# Proof by induction Q

1. May 20, 2013

### converting1

$$I_n = \displaystyle \int_0^1 (1-x^2)^ndx, n \geq 0$$

Given that $(2n + 1)I_n = 2nI_{n-1}$

proove by induction that

$I_n \leq \left (\dfrac{2n}{2n + 1} \right)^n$ for positive integers of n

in the solutions, could someone explain how they got to step 1, and why we need to show step 2 to complete the proof?

Solutions: http://gyazo.com/26e85134e4d5c13d5d7a49a0de91ae58

Last edited: May 20, 2013
2. May 20, 2013

### milesyoung

You have the statement:
$$S_n : I_n \leq \left( \frac{2n}{2n + 1} \right)^n$$
and you want to prove that it's true for all n, where n is a positive integer.
You can do this by proving that $S_1$ and $S_k \Rightarrow S_{k + 1}$ are true, where k is a positive integer.

Proving $S_1$ is true should be simple enough. Prove $S_k \Rightarrow S_{k + 1}$ is true by direct proof, i.e. assume $S_k$ to be true and show that it forces $S_{k + 1}$ to be true:
$$S_k : I_k \leq \left( \frac{2k}{2k + 1} \right)^k \Leftrightarrow \frac{2k + 2}{2k + 3} I_k \leq \frac{2k + 2}{2k + 3} \left( \frac{2k}{2k + 1} \right)^k \Leftrightarrow I_{k + 1} \leq \frac{2k + 2}{2k + 3} \left( \frac{2k}{2k + 1} \right)^k$$
Here I just multiplied both sides of the inequality by $\frac{2k + 2}{2k + 3}$ and used the relation $I_n = \frac{2n}{2n + 1} I_{n - 1}$.

You have:
$$S_{k + 1} : I_{k + 1} \leq \left( \frac{2(k + 1)}{2(k + 1) + 1} \right)^{k + 1} = \left( \frac{2k + 2}{2k + 3} \right)^{k + 1} = \left( \frac{2k + 2}{2k + 3} \right)^{1} \left( \frac{2k + 2}{2k + 3} \right)^{k}$$
Thus, if you can show that:
$$\frac{2k + 2}{2k + 3} \left( \frac{2k}{2k + 1} \right)^k \leq \left( \frac{2k + 2}{2k + 3} \right)^{1} \left( \frac{2k + 2}{2k + 3} \right)^{k}$$
then $S_{k + 1}$ must be true if $S_{k}$ is true.

It follows by induction that $S_n$ is true for all n, where n is a positive integer.

3. May 20, 2013

### converting1

managed to show that's true

thank you :)