Mathematical induction

[cenwee]

Hello guys, I have few questions...all mathematical induction problems.

I do know the mechanism for solving the induction problems, like doing the initialization, then the induction hypothesis and such. It's just that for some of these problems, I get stuck on the algebra on how to derive a statement from the another one (by statement, I mean P_K and P_K+1).

---

Q1. Using the principles of mathematical induction, I have to prove the below statement to be true.
1/(1x3) + 1/(2x4) + 1/(3x5) + ... 1/(n(n+2)) = n(3n+5)/4(n+1)(n+2)

So I did what I wrote down below,
step 1. initialization - I proved P₁ to be true by plugging in 1 to n
step 2. induction hypothesis - I assumed P_K to be true, and constructed a new statement P_K+1

P_K: 1/(1x3) + 1/(2x4) + 1/(3x5) + ... 1/(k(k+2)) = k(3k+5)/4(k+1)(k+2)
P_K+1: 1/(1x3) + 1/(2x4) + 1/(3x5) + ... 1/(k(k+2)) + 1/(k+1)(k+3) = (k+1)(3k+8)/4(k+2)(k+3)

Therefore,
k(3k+5)/4(k+1)(k+2) + 1/(k+1)(k+3) = (k+1)(3k+8)/4(k+2)(k+3)

My goal is to derive the right statement from factoring/simplifying/manipulating the left statement. I have tried various attempts, but in vain. I would really like some help...

---

Q2. Show that n ≤ 2^n-1 for all natural numbers n.


What I did was this:
P_K = k ≤ 2^k-1
P_K+1 = k+1 ≤ 2k

k+1 ≤ 2^k
k+1 ≤ 2 x 2^k-1
k ≤ 2 x 2^k-1 - 1 <--- and I got stuck here...(I don't even know if this is the right track to be honest)

Out of all induction problems this one is the most confusing to me, because I find it to be rather...abstract. It's like creating something out of nothing? I would really appreciate if someone could give me some advices on how to solve this kind of induction problems.

---

Q3. Show that 3 is a factor of n³+2n for all natural numbers n.

I did this:
P_K = k³+2k
P_K+1 = (k+1)³+2(k+1)

...and this is where I stopped. I did try, but it led me nowhere and I had this feeling that I wasn't on a right track...I am really helpless on this problem.



I would really appreciate some help on how to solve these problems, and just general advices on induction problems. Thank you in advance.

 

[pka]

Q3. Show that 3 is a factor of n³+2n for all natural numbers n.
I did this:
P_K = k³+2k
P_K+1 = (k+1)³+2(k+1)

\(\displaystyle (k+1)^3+2(k+1)\\ k^3+3k^2+3k+1+2k+2\\ [k^3+2k]+3[k^2+k+1]\)

That is clearly a multiple of three.

 

[Ishuda]

...
Q2. Show that n ≤ 2^n-1 for all natural numbers n.


What I did was this:
P_K = k ≤ 2^k-1
P_K+1 = k+1 ≤ 2k

k+1 ≤ 2^k
k+1 ≤ 2 x 2^k-1
...

or
k + 1 \(\displaystyle \le\) 2^k-1 + 2^k-1
Start at the end and go backwards: Since 1 \(\displaystyle \le\) k, we have 1 \(\displaystyle \le\) 2^k-1 and, by the induction assumption k \(\displaystyle \le\) 2^k-1. So we can add the two inequalities to get
k + 1 \(\displaystyle \le\) 2^k-1 + 2^k-1
k+1 ≤ 2 x 2^k-1
k+1 ≤ 2^k

...
Q3. Show that 3 is a factor of n³+2n for all natural numbers n.

I did this:
P_K = k³+2k
P_K+1 = (k+1)³+2(k+1)
...

You just have to play around. For me, I would probably tackle this in parts, i.e. We know that any natural number k can be written as 3j-1 or 3j or 3j+1 for some j. ... But, on to induction

P_k+1 = (k+1) [ (k+1)² + 2] = (k+1) (k² + 2k + 1 + 2)
= k (k² + 2k + 1 + 2) + k² + 2k + 1 + 2
= k (k² + 2) + k (2k + 1) + k² + 2k + 1 + 2
= P_k + 2 k² + k + k² + 2k + 1 + 2
= P_k + 3 k² + 3 k + 3
= P_k + 3 (k² + k + 1)

That leaves Q1. That is a more time consuming play around. I would approach this by multiplying through by [4 (k+1) (k+2) (k+3)] to get
k(3k+5)(k+3) + 4 (k+2) = (k+1)²(3k+8)
and start 'simplifying': First the left (or right) side, then the right (or left) side.
If you get stuck, show your work and we'll see what we can do to help