# Thread: [SOLVED] induction proof

1. ## [SOLVED] induction proof

This is my first post. I found this site when I was trying to find something online to get some help on some discrete math homework. Hopefully somebody can help me out.

I have four proofs that are the same basic type, that I just can't quite figure out. Here is an example:
(5^(n+1) + 2*3^n + 1) | 8 for all n >= {0,1,2,3,...}

here's what I have so far:
basis:
n=0 5^1 + 2*3^0 + 1 = 5 + 2 + 1 = 8 | 8 = 1
n=1 5^2 + 2*3^1 + 1 = 25 + 6 + 1 = 32 |8 = 4
so I believe the proposition is true

hypothesis: (5^(n+1) + 2*3^n + 1) | 8
going to: (5^(n+2) + 2*3^(n+1) + 1) | 8

(5^(n+2) + 2*3^(n+1) +1)
= (5*5^(n+1) + 2*3*3^n +1)
= (4*5^(n+1) + 5^(n+1) + 2*2*3^n + 2*3^n +1)
= 4(5^(n+1) + 3^n) + (5^(n + 1) +2*3^n + 1)

and this is as far as I've been able to get on all three of them.
I know that the last part (5^(n+1) + 2*3^n + 1) is divisible by 8 from the inductive hypothesis, but I can't figure out how to get the first part.

On another problem I factor out 5 from the first part but I'm trying to get it divisible by 10, and a third problem I factored out 4 trying to get it divisible by 16.

Any help would be greatly appreciated.

2. Welcome to the forums, mate.

Ok, so you've proved the base case. Now we assume that n=k is true, that is,

$\displaystyle 5^{k+1} + 2(3^k) + 1 = 8a$ where $\displaystyle a$ is an integer.
This can be rewritten as
$\displaystyle 5^{k+1} = 8a - 2(3^k) -1$

Now consider n=k+1

$\displaystyle 5^{k+2} + 2(3^{k+1}) +1$
$\displaystyle = 5(8a - 2(3^k) -1) + 2(3^{k+1}) +1$ (by induction hypothesis)
$\displaystyle = 40a -10(3^k) -5 + 6(3^k) +1$
$\displaystyle = 40a - 4(3^k) -4$
$\displaystyle = 4(10a -3^k -1)$
$\displaystyle = 4(10a - (3^k +1))$
But you know that $\displaystyle 10a - (3^k +1)$ is always even. So you can say that $\displaystyle 10a - (3^k+1) = 2l$ where l is an integer.

so you're left with $\displaystyle 4(2l) =8l$. Thus it is divisible by 8.

3. Originally Posted by jimboruss
This is my first post. I found this site when I was trying to find something online to get some help on some discrete math homework. Hopefully somebody can help me out.

I have four proofs that are the same basic type, that I just can't quite figure out. Here is an example:
(5^(n+1) + 2*3^n + 1) | 8 for all n >= {0,1,2,3,...}

here's what I have so far:
basis:
n=0 5^1 + 2*3^0 + 1 = 5 + 2 + 1 = 8 | 8 = 1
n=1 5^2 + 2*3^1 + 1 = 25 + 6 + 1 = 32 |8 = 4
so I believe the proposition is true

hypothesis: (5^(n+1) + 2*3^n + 1) | 8
going to: (5^(n+2) + 2*3^(n+1) + 1) | 8

(5^(n+2) + 2*3^(n+1) +1)
= (5*5^(n+1) + 2*3*3^n +1)
= (4*5^(n+1) + 5^(n+1) + 2*2*3^n + 2*3^n +1)
= 4(5^(n+1) + 3^n) + (5^(n + 1) +2*3^n + 1)

and this is as far as I've been able to get on all three of them.
I know that the last part (5^(n+1) + 2*3^n + 1) is divisible by 8 from the inductive hypothesis, but I can't figure out how to get the first part.

On another problem I factor out 5 from the first part but I'm trying to get it divisible by 10, and a third problem I factored out 4 trying to get it divisible by 16.

Any help would be greatly appreciated.
As you no doubt realise, you need a cunning manipulation:

$\displaystyle 5^{k+2} + 2 \times 3^{k+1} + 1 = 5\left( 5^{k+1} + 2 \times 3^k + 1 \right) - (4 \times 3^k + 4)$.

The first term is clearly divisible by 8 by the inductive hypothesis.

As for the second term, note that $\displaystyle 4 \times 3^k + 4 = 4 (3^k + 1)$. Can you prove (by induction, perhaps) that 3^k + 1 is always divisible by 2 when k is a positive integer. It then follows that the second term is divisible by 8 .....

4. ## Thank you

Thank you WWTL@WHL and mr fantastic. You two are both my heroes. I never even thought of using induction a second time.

5. Originally Posted by jimboruss
[snip] I never even thought of using induction a second time.
Yeah well, I fiddled around for a few moments but couldn't see a simple way of re-arranging $\displaystyle 3^k + 1$ so that 2 was obviously a factor (someone will come along now and make me look a complete chump).

But intuitively you know that $\displaystyle 3^k + 1$ is even and therefore MUST be divisible by 2.

But intuition is not a proof ..... Proof by induction can sometimes be an excellent tool for proving something true when you know intuitively that it is true.