Hello! Please help me on an induction question.

Question

Show that 5^(3^n) + 1 is divisible by 3^(n + 1) for all non-negative integers n.

I have made very little progress. Here's what I have so far:
Let n=1. We have 5^3 + 1 = 3^2.

Thanks in advance for the help.

Answer 1

well, you got step 1.
Now, assuming P(n), what about P(n+1)?
5^(3^(n+1))+1 = 5^(3*3^n)+1 = (5^(3^n))^3 + 1
Now, since a^3+b^3 = (a+b)(a^2-ab+b^2) we have
(5^(3^n))^3 + 1 = (5^(3^n)+1)((5^(3^n))^2 - 5^(3^n) + 1)
But, since 5^(3^n)+1 is divisible by 3^(n+1) so is that product.
So, P(n) ==> P(n+1)
QED

Answer 2

step 1: let n = 1
is 5^(3^1) + 1 divisible by 3^(1 + 1) ??
well, 5^(3^1) + 1
= 125 + 1 = 126
and 3^2 = 9
is 126 divisible by 9? YES

step 2: assume it is true for n = k
that is: 5^(3^k) + 1 is divisible by 3^(k + 1)

step 3: show that then 5^(3^(k+1)) + 1 is divisible by 3^(k+1 + 1)

basic numeric principle: if a is divisible by x and b is divisible by x
then (a-c) is divisible by x
e.g. 486 is divisible by 6, and 210 is divisible by 6
then (486-210) or 276 is also divisible by 6

so 5^(3^(k+1)) + 1 - (5^(3^k) + 1)
= 5^(3^(k+1)) - (5^(3^k) , this should be divisible by 3^(k+2)
= 5^(3^k) (5^(3^(k+1 - 3k) - 1) <------- hitting a mental block, this factoring is harder than it seems

---- e.g. If n = 5
5^(3^6) - 5^(3^5) = 5^(3^5) (5^(3^6 - 3^5) - 1)
= 5^486 - 1 is that divisible by 3^8 ???

= 5^(3^k) (..???....) <

Answer 3

oobleck the saviour!!

Answer 4

Thanks a lot, oobleck and Reiny! I understand it now :)

Answer 5

this question is copy righted