# Thread: Could someone check this induction?

1. ## Could someone check this induction?

Could someone please check this induction proof, unsure if this is the correct way to go about it.

Prove by induction that $\displaystyle 9 \times 4^n + 5 \times 11^n$ is divisible by 7 for all non negative integers $\displaystyle n$.

Initial step, $\displaystyle n=0$

$\displaystyle 9 \times 4^0 + 5 \times 11^0 = 14$, therefore true for $\displaystyle n=0$.

Induction step. Assume for $\displaystyle n=k$, therefore $\displaystyle 9 \times 4^k + 5 \times 11^k = 7a$ for some $\displaystyle a$.

Therefore for $\displaystyle n=k+1$ we have:

$\displaystyle 9 \times 4^{k+1} + 5 \times 11^{k+1}$

$\displaystyle 9(4^k) + 9(4) + 5(11^k) + 5(9)$

$\displaystyle 9(4^k) + 5(11^k) + 9(4) + 5(9)$

$\displaystyle 7a + 91$

$\displaystyle 7(a + 13)$.

Therefore true for all $\displaystyle n$.

2. Originally Posted by craig
Could someone please check this induction proof, unsure if this is the correct way to go about it.

Prove by induction that $\displaystyle 9 \times 4^n + 5 \times 11^n$ is divisible by 7 for all non negative integers $\displaystyle n$.

Initial step, $\displaystyle n=0$

$\displaystyle 9 \times 4^0 + 5 \times 11^0 = 14$, therefore true for $\displaystyle n=0$.

Induction step. Assume for $\displaystyle n=k$, therefore $\displaystyle 9 \times 4^k + 5 \times 11^k = 7a$ for some $\displaystyle a$.

Therefore for $\displaystyle n=k+1$ we have:

$\displaystyle 9 \times 4^{k+1} + 5 \times 11^{k+1}$

$\displaystyle 9(4^k) + 9(4) + 5(11^k) + 5(9)$

What, in the holy name of the Great Pumpkin, did you do here??!:

$\displaystyle 9\cdot 4^{k+1}=9\cdot 4^k\cdot 4=36\cdot 4^k$, and the same with the other term, so you need to correct this QUICKLY and think over your proof again.

Tonio

$\displaystyle 9(4^k) + 5(11^k) + 9(4) + 5(9)$

$\displaystyle 7a + 91$

$\displaystyle 7(a + 13)$.

Therefore true for all $\displaystyle n$.
.

3. Originally Posted by tonio
.
According to my teacher the steps should be as follows:
1. Show that it is true for n=1.
2. Assume that it is true for n=k.
3. Show that the truth of n=k implies the truth of n=k+1

then your equation is true for all natural numbers.

4. Assume $\displaystyle 9\cdot4^n+5\cdot11^n = 7k$.

Then $\displaystyle 9\cdot3\cdot4^n+5\cdot10\cdot11^n+9\cdot4^n+5\cdot 11^n = 9\cdot3\cdot4^n+5\cdot10\cdot11^n +7k = 21k+5\cdot7\cdot11^n+7k$.

Therefore $\displaystyle 9\cdot4^{n+1}+5\cdot11^{n+1} = 7(5\cdot11^n+4k)$.

5. Originally Posted by chiph588@
Assume $\displaystyle 9\cdot4^n+5\cdot11^n = 7k$.

Then $\displaystyle 9\cdot3\cdot4^n+5\cdot10\cdot11^n+9\cdot4^n+5\cdot 11^n = 9\cdot3\cdot4^n+5\cdot10\cdot11^n +7k = 21k+5\cdot7\cdot11^n+7k$.

Therefore $\displaystyle 9\cdot4^{n+1}+5\cdot11^{n+1} = 7(5\cdot11^n+4k)$.

That was a weird, and not so natural imo, way to reach the result:

$\displaystyle 9\cdot 4^{k+1}+5\cdot 11^{k+1}=36\cdot 4^k+55\cdot 11^k= 4\left(9\cdot 4^k+5\cdot 11^k\right)+35\cdot 11^k$

And the first term is divisible by 7 because of the ind. hyp., and the second one is obviously divisible by 7, so we're done.
Tonio

6. Ahh thankyou for the replies. Not quite sure what I managed to do there, that's what you get for doing proofs at 11 at night!

Thanks for all the replies, very helpful.

7. Originally Posted by craig
Ahh thankyou for the replies. Not quite sure what I managed to do there, that's what you get for doing proofs at 11 at night!

Thanks for all the replies, very helpful.
Induction proofs can be tricky once you get to the implication step. Remember that you are going to use the assumption that P(k) is true when showing P(k+1) follows. If you ever find yourself ending up like you did with P(k+1) seeming to be true regardless of P(k), you should back up.

Also, just like integrals, induction proofs have different forms and call for different techniques. Once you practice all of the techniques and know what type of problem they go with, it all becomes easier.

I myself have not become familiar with many induction situations and can only notice the divisibility situation or the summation one. I actually couldn't figure this one out last night because I couldn't see the way needed to split up the terms such that the condition is satisfied. This is advice to myself as well as you