# Thread: proving (by induction)

1. ## proving (by induction)

Suppose the numbers a0,a1,a2,....,an satisfy the following conditions:

a0= 1/2, ak+1 =ak + (1/n) ((ak)^2) for k=0,1,2,...,n-1.

Prove that (n+1)/(
2n-k+2) <ak < (n)/(2n-k )

for k=1,2,3,....,n

2. The statement doesn't make sense for n=0 !

We'll prove it for every natural number n>0 by induction on k.

Base case: k=1.

$a_1 = \frac{1}{2}+\frac{1}{4n} = \frac{2n+1}{4n}$

$\frac{n+1}{2n-1+2} < \frac{2n+1}{4n}$ iff $4n(n+1) < (2n+1)(2n+1)$ iff $4n^2+4n < 4n^2+4n+1$ and this is true for every n>0.

$\frac{2n+1}{4n} < \frac{n}{2n-1}$ iff $4n^2-1 < 4n^2$ and this is true for every n>0.

Base case verified.

Let for arbitrary n>0

$\frac{n+1}{2n-k+2} $\;$ $\;$ $\;$ $\;$ (1)

hold for some 0<k<n . We want to show that (1) also holds for k+1, i.e. we want

$\frac{n+1}{2n-k+1} < a_k+\frac{1}{n}a_k^2 < \frac{n}{2n-k-1} \;$ $\;$ $\;$ $\;$ $\;$ (2)

to hold.
From the second inequality in (1) we have $a_k+\frac{1}{n}a_k^2 < \frac{n}{2n-k} + \frac{1}{n} \left(\frac{n}{2n-k}\right)^2 = \frac{n(2n-k+1)}{(2n-k)^2}$ and this is strictly less than $\frac{n}{2n-k-1}$ iff $4n^3-4kn^2+k^2n-n < 4n^3-4kn^2+k^2n$ which is equivalent to $-n<0$ which is true because n>0.

So the second inequality in (2) is verified.

From the first inequality in (1) we have $a_k+\frac{1}{n}a_k^2 > \frac{n+1}{2n-k+2}+\frac{1}{n}\left(\frac{n+1}{2n-k+2}\right)^2 = \frac{(n+1)(2n^2-kn+3n+1)}{n(2n-k+2)^2}$ and this is strictly greater than $\frac{n+1}{2n-k+1}$ iff $4n^4-4n^3k+12n^3+k^2n^2-8kn^2+13n^2+k^2n-5kn+6n-k+1>$

$> 4n^4-4n^3k+12n^3+k^2n^2-8kn^2+12n^2+k^2n-4kn+4n$ which is equivalent to $n^2-kn+2n-k+1>0$.

Now because k<n we have $n^2-kn+2n-k+1> n^2-n^2+2n-n+1 = n+1 > 0$, no doubt.

So the first inequality in (2) is also verified and thus the induction step is completed and the proof is finished.