Discrete Math Proof

>>8334397
Just induct it, bro.

>>8334397
This is really obvious. If there are more than 0 ways of choosing a sequence of positive integers n_k, then there is a maximum positive integer n_M. Clearly, any k length sequences that feature positive integers greater than n_M will not satisfy the equation, as every reciprocal generated by the new sequence is less than every reciprocal generated by the n_k sequence. Now that we have proved that we can only choose k positive integers between 1 and n_M, there are clearly only finitely many choices we can make, therefore, for every real number r, and every positive integer k, there are either no k length sequences of positive integers that solve the equation, or there are finitely many. (Clearly, we aren't supposed to include longer length sequences in the sum of reciprocals, as you can just turn 1(n_i) = 1/(2*n_i) + 1/(2*n_i), which would allow you to make infinitely many sequences of positive integers).

>>8334440
*that only include integers greater than n_M

>>8334440
>then there is a maximum positive integer n_M
you what

>>8334460
In any set of k positive integers (that form the sequence n_k), there is a maximum integer n_M.

>>8334586
Yes but there is no maximum possible n_M which your proof seems to argue at the end.

>>8334397
Consider the set of solution tuples [math] (n_1, n_2, ..., n_k) [/math] for a given r, and also assume that these tuple entries are sorted least to greatest. Now if you think about the set of all [math] n_1 [/math] values, we can tell that it must be bounded, otherwise we couldn't reach r. Thus there must be some [math] n_1 [/math] value present in infinitely many other solution tuples, so we induct on [math] r - n_1 [/math], and once we reach tuples of a single value, we arrive at a contradiction, since there aren't infinitely many ways of writing r as [math] \frac{1}{n_1} [/math].

>>8334731
How do you know n1 has a max?

>>8334397
We will assume the list is ordered from smallest natural number to largest.

Given k. For each r, there exists a smallest natural number N such that k/N is less than r. Then n_1 cannot be larger than N. Then for r-(1/n_1), we have another real number and need k-1 numbers. By induction (and work out the base case) the proof is done

>>8334766
We required [math] n_1 [/math] to be the smallest in the tuple, meaning that [math] \frac{1}{n_1} [/math] is the greatest value in the sum of r for the particular solution it's in, so all the other values in the sum are less than or equal to [math] \frac{1}{n_1} [/math]. Therefore, the sum [math] \frac{1}{n_1} + ... + \frac{1}{n_k} [/math] is at most [math] \frac{1}{n_1} + ... + \frac{1}{n_1} = \frac{k}{n_1} [/math]. Thus we get the inequality [math] \frac{k}{n_1} \ge r [/math], which implies that [math] \frac{k}{r} \ge n_1 [/math], or that [math] n_1 [/math] is bounded.

>>8334397
the smallest n can ever be is 1, and this presents a solution only when r=k, therefore 0<r<=k for any solution that exists. Since n can never be smaller than 1, an all 1 solution is unique, because to increase any particular n makes the sum fall short, but we have no way to increase it by making other terms >1.

Suppose we have a solution that isn't all 1s. Sort these by <. To construct a different solution, some n term must be made larger. Doing so means necessarily that some adjustment must be made to at least one other term to its right in order for the sum to hold. But since we can never make n less than 1, and since there are only finite terms to the right, we cannot adjust indefinitely, therefore there must be a finite number of solutions.

>>8334615
In any finite set of positive integers, there is a largest integer. And because of this, you don't have to test any k length sequences of positive integers where all of the positive integers are bigger than n_M. Hence, we limit both the length of the sequence to k, and we limit the sizes of the positive integers to n_M, and if r doesn't have an Egyptian fraction decomposition, then there are 0 possibilities, which is a finite number, hence, there are only finitely many possible combinations for every pair (r,k).

Seeing as this is the DS thread

How do you guys learn this subject best?

Any textbooks, websites, tricks, tips?

Start with the case k=1. If r is the inverse of a natural number, then there is exactly one solution by the uniqueness of inverses, and otherwise there are no solutions (which is still finite).

Now, suppose there are only finitely many solutions for the case of k. Then, the theorem holds for k+1, as r-(1/n) is again real, and we have reduced the problem to the case of k again.

By induction over k, we have that the theorem holds for all natural numbers k.

(Note that this prov holds for k=0, as the corresponding equation has at most one solution, occurring when r=0, as 0 is the empty sum. This is strictly stronger than the theorem in the picture.)

>>8334397
I've got a pretty easy solution:
Assume that r is irational. If you work out the left side by adding the (1/n_i )'s, the left member would be rational. Thus, r can't be irational.
Since r is rational( r=p/q), if you work out the left side you get that n_i's must be divisors of q. Then, at most, the number of solutions would be nr_of_divisors_of_q at the power k( you get that from cartesian product).Which is finite. Qed
Sorry for grammar mistakes( if any ).

>>8335874
Nice proof, anon.

>>8335882
I'm glad you liked it. Last night i really had no clue how to start doing anything in order to solve it, but i remembered the problem when i woke up today and solved it in my mind.

>>8335874
>r can't be irrational
This implies the equality doesn't hold for every real number greater than zero, whilst we're trying to prove the assertion for all real numbers r -- including irrational numbers -- greater than zero.

>>8336288
it clearly doesn't hold for irrationals. the sum of rationals (1/ni) is rational. pay attention will you?

>>8336288
It only says there is a finite solution set over the naturals. If r is irrational, the solution set is certainly finite: it's empty.

>>8335146
Not quite, yes (r - 1/n) is real, but there are an infinite number of different n's to choosefrom for a sufficiently large n. For each n, the solution set is finite (by inductive hypothesis), but we do not know if the union of all the solution sets (for r - 1/n) is finite as well, which is what is required for an inductive step.

>>8335874
>if you work out the left side you get that n_i's must be divisors of q

2/1 = 1/1 + 1/3 + 1/3 + 1/3

But 3 is not a divisor of 1.

>>8334731
>>8334787

Good proof anon

>>8337006
Good point anon, thank you. The proof is sound with that added to the inductive step though, yes?

>>8334787
you can use that and induct on [math]k[/math]

>>8335874
This is flawed, as each [math]n_i[/math] needs not be coprime with [math]\sum_{j=1}^k \prod_{l=1,l\neq j} n_l[/math]

>>8337012
>>8335874
Alright, i know what i messed up.
When the r=p/q, after you work out the left side and have nominators/(product_of n_i) = p/q, then since all the numbers are integers and p/q is irreductible, you get that (E) c, c an integer so that (product_of n_i)= q * c; so now i think it's done.

>>8337792
all you get is [math]q\cdot \sum_{j=1}^k \prod_{l=1,l\neq j} n_l = p\cdot \prod_{i=1}^k n_i[/math]

Even with [math]p[/math] and [math]q[/math] being coprime, there's nothing more you can say.

Your proof is not salvageable

>>8337937
From that equation of yours, you can't see it that well. I might be wrong, but from : nominators/(product_of n_i) = p/q, you know that since both sides are equal, the left side can be simplified by a number c. And it's quite obv that c is an integer( that could also be 1). Isn't it?

>>8337937
>>8337984
Nvm, you're right.

>>8334397
Choose [math] n_{1},...,n_{k}[/math] such that [math]n_{1}=...=n_{k}[/math]

we kan now write, [math]N\frac{1}{n_{1}}=r[/math].
furthermore if we choose [math]r[/math] to be fixed we can let [math]N[/math] depend on [math]n_{1}[/math]
letting [math]r = 2[/math] we get [math]N=2n_{1}[/math].

the observant lurker should have spotted by now,
that there are infinitely many sollutions to [math]N=2n_{1}[/math]

this concludes the proof that OP is a fag [math]\blacksquare[/math]