Expert: Paul Klarreich - 11/17/2008

Question
Hi,
I need to solve a problem by MI:
Show 16^n+10n-1 is divisible by 25 for any value of n.
I made sure that n=1 worked and made the assumption that n=k also works. From there I don't know how to prove that k+1 also works after plugging it in the equation.


Answer
Questioner:   Ryan
Category:  Advanced Math
Private:  No
 
Subject:  Mathematical Induction
Question:  Hi,
I need to solve a problem by MI:
Show 16^n+10n-1 is divisible by 25 for any value of n.
I made sure that n=1 worked and made the assumption that n=k also works. From there I don't know how to prove that k+1 also works after plugging it in the equation.
.............................
Hi, Ryan,

The key word in M.I. is WRITE.  (btw, don't use the letters M.I. in your doctor's office.  To him it means 'heart attack.')

1. WRITE the theorem for n = 1.  Verify it. (OK, you did this.)
............

2. WRITE the theorem for n = k.  This is your assumption.  So you wrote:

Assume  16^k + 10k - 1 = 25M for some M.

or  16^k = 25M - 10k + 1  << convenient thing to substitute
...............

3. WRITE the theorem for n = k+1.  This is to be proved.  So you wrIte:

To prove: 16^(k+1) + 10(k+1) - 1 = 25P, for some P.

16^(k+1) + 10(k+1) - 1 =
16(16^k) + 10k + 10 - 1 =  
16(16^k) + 10k + 9 =

16(insert here from the assumption) + 10k + 9 =

16(25M - 10k + 1) + 10k + 9 =

400M - 160k + 16 + 10k + 9

400M - 150k + 25

25(16M - 6k + 1) = 25P

DONE.

=================================

Now here is a nice trick for 'divisibility' proofs.  

Want to prove that 25 | B when you know 25 | A?

Prove that 25 | (B-A).  That is, if 25 divides the difference of two numbers, and 25 divides one, it must divide the other.

It probably does not make this one easier, but it is worth remembering.