proving (by induction)

**nh149** · August 30th 2009, 08:29 AM

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

**Taluivren** · August 30th 2009, 04:50 PM

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}<a_k<\frac{n}{2n-k} \;$ $\;$ $\;$ $\;$ $\;$ (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.

Thread: proving (by induction)

LinkBack

Thread Tools

Display

proving (by induction)

Similar Math Help Forum Discussions

Proving an inequation with induction

Using my assumption when proving by induction

Need help proving mathematical induction

few problems on proving using induction

Need help proving!! Mathematical Induction

Search Tags