# Thread: I need help to prove 2 Induction

1. ## Re: I need help to prove 2 Induction

No problem, we are glad to help!

Induction has three main parts.
Part 1: Prove a base of induction. Choose a base case and prove that the hypothesis holds true for that base case.
Part 2: Induction step. Assume that the induction hypothesis holds true for some natural number $n$.
Part 3: Using the assumption that the induction hypothesis holds true, prove that the hypothesis holds true for $n+1$.

2. ## Re: I need help to prove 2 Induction

When the problem itself involves "n" I prefer to use "it is true for n= k" and then prove "it is true for k+1", using "k" rather than "n". That way people do not confuse the "induction hypothesis" with the proposition to be proved.

3. ## Re: I need help to prove 2 Induction

Hi,
I can't solve it , you could please give me example on the second exercise and I will solve the first one alone ,
Thanks.

4. ## Re: I need help to prove 2 Induction

Why are you having trouble solving it? It is much easier to help when you have specific questions. What makes this difficult is that I have no idea of your level of mathematical knowledge. I assume you are familiar with partial sums of the harmonic series. Are you familiar of its relationship with the natural logarithm? How about the digamma function? Does it help for me to point out that:

$\displaystyle \dfrac{1}{2^k} + \dfrac{1}{2^k+1} + \dfrac{1}{2^k+2} + \cdots + \dfrac{1}{2^{k+1}-1} = \psi^{(0)}\left( 2^{k+1} \right) - \psi^{(0)} \left( 2^k \right)$?

If that does not help, please try the problem on your own and ask specific questions when you get stuck.

5. ## Re: I need help to prove 2 Induction

Perhaps this will help more.

$\displaystyle \dfrac{1}{2} = 2^k\cdot \dfrac{1}{2^{k+1}} = \underbrace{\dfrac{1}{2^{k+1}} + \dfrac{1}{2^{k+1}}+\dfrac{1}{2^{k+1}}+\cdots + \dfrac{1}{2^{k+1}}}_{2^k\text{ terms}} < \underbrace{\dfrac{1}{2^k}+\dfrac{1}{2^k+1}+\dfrac {1}{2^k+2}+\cdots + \dfrac{1}{2^{k+1}-1}}_{2^k\text{ terms}} \le \underbrace{\dfrac{1}{2^k} + \dfrac{1}{2^k}+\dfrac{1}{2^k}+\cdots + \dfrac{1}{2^k}}_{2^k\text{ terms}} = 2^k\cdot \dfrac{1}{2^k} = 1$