Need help with a proof by induction, please

  • Thread starter yelena0000
  • Start date
  • #1
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.
please help
 

Answers and Replies

  • #2
Hitman2-2
and i know that next i have to prove for n=k+1 but i really have no idea what to do with that.

If you substitute n = k + 1, you get

[tex]
3^{2(k+1) - 1} + 1 = 3^{2k-1} 3^2 + 1
[/tex]

By assumption, [tex] 4 | 3^{2k-1} + 1 [/tex] so try to re-write [tex] 3^{2k-1} 3^2 + 1 [/tex] in a form that has a factor of [tex] 3^{2k-1} + 1 [/tex].
 
  • #3
statdad
Homework Helper
1,495
36
The general term is

[tex]
a_n = 3^{2n-1}+1
[/tex]

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 [tex] a_{k+1} [/tex].

[tex]
3^{2(k+1)-1} +1 = 3^{2k+2-1} + 1 = 3^{2k -1} 3^2 + 1
[/tex]

The goal is to show that this is also divisible by four - the fact that [tex] a_k [/tex] is divisible by four will play a role in this.
 
Last edited by a moderator:

Related Threads on Need help with a proof by induction, please

  • Last Post
Replies
5
Views
1K
Replies
2
Views
6K
Replies
4
Views
2K
Replies
4
Views
970
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
15
Views
3K
  • Last Post
Replies
24
Views
2K
Replies
9
Views
1K
  • Last Post
Replies
3
Views
649
  • Last Post
Replies
5
Views
1K
Top