Discrete Math Proof

Tits for answers to this

Just induct it, bro.

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).

*that only include integers greater than n_M

>then there is a maximum positive integer n_M
you what

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

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

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].

How do you know n1 has a max?

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

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.

the smallest n can ever be is 1, and this presents a solution only when r=k, therefore 0

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.)

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 ).

Nice proof, user.

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.

>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.

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

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.

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.

>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.

Good proof user

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

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

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]

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.

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

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?

Nvm, you're right.

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]