# Need help with a proof by induction, please

1. Sep 4, 2008

### yelena0000

Using proof by induction, prove that (3^(2n-1))+1 is divisible by 4

so this is what i could do so far:

for n=1
3^(2*1-1)+1=4 which is divisible by 4
assume truth for n=k
(3^(2k-1))+1 is divisible by 4
and i know that next i have to prove for n=k+1 but i really have no idea what to do witht that.

2. Sep 4, 2008

### Hitman2-2

If you substitute n = k + 1, you get

$$3^{2(k+1) - 1} + 1 = 3^{2k-1} 3^2 + 1$$

By assumption, $$4 | 3^{2k-1} + 1$$ so try to re-write $$3^{2k-1} 3^2 + 1$$ in a form that has a factor of $$3^{2k-1} + 1$$.

3. Sep 4, 2008

The general term is

$$a_n = 3^{2n-1}+1$$

and you've shown that $a_1$ is divisible by four, and you've assumed the same for $a_k$ for some $k \ge 1$.

Look at $$a_{k+1}$$.

$$3^{2(k+1)-1} +1 = 3^{2k+2-1} + 1 = 3^{2k -1} 3^2 + 1$$

The goal is to show that this is also divisible by four - the fact that $$a_k$$ is divisible by four will play a role in this.

Last edited by a moderator: Sep 4, 2008