SOLUTION: Use mathematical induction to prove: 4^n+1 + 5^2n-1 is divisible by 21

Algebra ->  Sequences-and-series -> SOLUTION: Use mathematical induction to prove: 4^n+1 + 5^2n-1 is divisible by 21      Log On


   

Question 170325: Use mathematical induction to prove: 4^n+1 + 5^2n-1 is divisible by 21
Found 2 solutions by jim_thompson5910, Edwin McCravy:
Answer by jim_thompson5910(35256) About Me  (Show Source):
You can put this solution on YOUR website!
Note: I'm assuming that the assumption holds for n%3E=1



Step 1)

Prove for n=1

which is divisible by 21



-----------------------------------------------


Step 2)


Assume 4%5E%28k%2B1%29+%2B+5%5E%282k-1%29 is divisible by 21 (ie assume kth term is divisible by 21)


-----------------------------------------------


Step 3)


Prove true for k+1 term


4%5E%28k%2B1%29+%2B+5%5E%282k-1%29 Start with the assumed portion


4%5E%28k%2B1%2B1%29+%2B+5%5E%282%28k%2B1%29-1%29 Plug in k+1 for every k


4%5E%28k%2B1%2B1%29+%2B+5%5E%282k%2B2-1%29 Distribute


4%2A4%5E%28k%2B1%29+%2B+5%5E2%2A5%5E%282k-1%29 Break up the exponent


4%2A4%5E%28k%2B1%29+%2B+25%2A5%5E%282k-1%29 Square 5 to get 25


4%2A4%5E%28k%2B1%29+%2B+4%2A5%5E%282k-1%29%2B21%2A5%5E%282k-1%29 Break up 25 to get 4+21


4%284%5E%28k%2B1%29+%2B+5%5E%282k-1%29%29%2B21%2A5%5E%282k-1%29 Factor out the GCF 4


Since we're assuming that 4%5E%28k%2B1%29+%2B+5%5E%282k-1%29 is divisible by 21, this means that 4%5E%28k%2B1%29+%2B+5%5E%282k-1%29=21m for some integer "m"


4%2821m%29%2B21%2A5%5E%282k-1%29 Replace 4%5E%28k%2B1%29+%2B+5%5E%282k-1%29 with 21m


Now let n=5%5E%282k-1%29 (which is an integer)


4%2821m%29%2B21n Replace 5%5E%282k-1%29 with "n"


21%284m%2Bn%29 Factor out the GCF 21



Now let j=4m%2Bn so the expression becomes


21j


Since 21 is a factor of 21j, this shows that 4%5E%28k%2B1%2B1%29+%2B+5%5E%282%28k%2B1%29-1%29 is divisible by 21.


So this proves that 4%5E%28n%2B1%29+%2B+5%5E%282n-1%29 is divisible by 21 for n%3E=1

Answer by Edwin McCravy(20056) About Me  (Show Source):
You can put this solution on YOUR website!
Use mathematical induction to prove: 4%5E%28n%2B1%29+%2B+5%5E%282n-1%29 is divisible by 21
Edwin's proof:

Let f%28n%29=4%5E%28n%2B1%29+%2B+5%5E%282n-1%29

First prove that there is at least one
value of n for which f%28n%29 is divisible by 21:

4%5E%28n%2B1%29+%2B+5%5E%282n-1%29
4%5E%281%2B1%29+%2B+5%5E%282%2A1-1%29
4%5E%282%29+%2B+5%5E%282-1%29
16+%2B+5%5E%281%29
16%2B5
21

Strategy:
If n=k is a value of n so that f(n=k) is divisible by 21,
then if f(k+1) and f(k) differ by a multiple of 21, then 
f(k+1) will also be divisible by 21.

So, we will consider the difference f(k+1)-f(k)  

But first we must calculate f(n=k+1):

f%28n%29=4%5E%28n%2B1%29+%2B+5%5E%282n-1%29
f%28k%2B1%29=4%5E%28%28k%2B1%29%2B1%29+%2B+5%5E%282%28k%2B1%29-1%29
f%28k%2B1%29=4%5E%28k%2B1%2B1%29%2B5%5E%282k%2B2-1%29
f%28k%2B1%29=4%5E%28k%2B2%29%2B5%5E%282k%2B1%29

Now we consider 



And since we know that since f(1) is divisible by 21
then f(2) is also divisible by 21, and thus f(3) is
also divisible by 21, etc., etc.

Edwin