Question

Hi there, I'm trying to work out a proof: Prove by induction on n that, for all positive integers n, 3 divides (4^n)+5... I'm half way there, but can't figure out how to deduce the P(n+1) case to prove the inductive step. Thx

Answer 1

are you sure this fact is true and if so this may still not be proovable. Many arithmatic facts cannot be proven because the incompletness theorem of Godel. To me this fact appears umprovable. Induction does not look like it would work you would need to turn P(n + 1) into P(n) + K where K is 0 = mod(3) which may not be possible.

Answer 2

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

3*4^n mod 3 =0 because of the factor 3, you can divide it by 3

P(n) mod 3 =0
=>
P(n)+3*4^n mod 3 = 0
=>
P(n+1) mod 3 = 0

Answer 3

what level of math have you guys been though If you don't mind my asking. I think your up there with me :)

Answer 4

Nice one suppe.

Answer 5

Here ya go.
Proof: We use induction on n. If 3 divides (4^n)+5 then (4^n)+5=3q for some integer q.
Base case: If n=1, 4+5=9=3*3, proving the base case.
Inductive step: Suppose as inductive hypothesis that (4^k)+5=3q for some integers k and q. Then (4^k+1)+5=3p for some integer p (by inductive hypothesis). Now, 4*(4^k)+20-15 = 4((4^k)+5)-15 = 4(3q)-15 = 3(4q-5), proving the inductive step as required.
Hence, 3 divides 4^n+5 for all n in the positive integers.

Answer 6

you could also generalize it to all integers of the form \[|4^n+5|\]