Could someone check this induction?

**craig** · November 29th 2009, 01:52 PM

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

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

Initial step, $n=0$

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

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

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

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

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

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

$7a + 91$

$7(a + 13)$ .

Therefore true for all $n$ .

**tonio** · November 29th 2009, 03:43 PM

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 $9 \times 4^n + 5 \times 11^n$ is divisible by 7 for all non negative integers $n$ .

Initial step, $n=0$

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

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

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

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

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

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

:

$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

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

$7a + 91$

$7(a + 13)$ .

Therefore true for all $n$ .

.

**mamen** · November 29th 2009, 05:49 PM

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.

**chiph588@** · November 29th 2009, 06:10 PM

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

Then $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 $9\cdot4^{n+1}+5\cdot11^{n+1} = 7(5\cdot11^n+4k)$ .

**tonio** · November 29th 2009, 06:52 PM

Originally Posted by chiph588@

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

Then $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 $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:

$9\cdot 4^{k+1}+5\cdot 11^{k+1}=36\cdot 4^k+55\cdot 11^k=<br /> 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

**craig** · November 30th 2009, 01:13 AM

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.

**Jameson** · November 30th 2009, 02:11 AM

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

Thread: Could someone check this induction?

LinkBack

Thread Tools

Display

Could someone check this induction?

Similar Math Help Forum Discussions

[SOLVED] need to check strong induction proof

work check please... check if a set spans a vector space and linear dependance

Rigorously prove the principle of complete induction from mathematical induction??

Induction check

Mathemtical Induction Proof (Stuck on induction)

Search Tags