Hello! Please help me on an induction 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.

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

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) (..???....) <

oobleck the saviour!!

this question is copy righted

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

To prove that 5^(3^n) + 1 is divisible by 3^(n + 1) for all non-negative integers n, we will use mathematical induction.

First, we have established the base case for n=1. We have shown that when n=1, 5^3 + 1 is equal to 3^2. This is a good starting point.

Now, we assume that the statement holds true for some arbitrary positive integer k, i.e., we assume that 5^(3^k) + 1 is divisible by 3^(k + 1).

Next, we aim to prove the statement for the next positive integer, k+1, i.e., we aim to show that 5^(3^(k+1)) + 1 is divisible by 3^(k + 2).

To simplify this expression, we can rewrite 5^(3^(k+1)) as (5^(3^k))^3. This can be done based on the property of exponentiation, where (a^b)^c is equal to a^(b*c).

Therefore, our expression becomes ((5^(3^k))^3) + 1.

Now, let's expand this expression:

= (5^(3^k))^3 + 1

= (5^(3^k))^3 + 1^3

= (5^(3^k))^3 + 1^3

= (5^(3^k))^3 + 1^3

= (5^(3^k) + 1)(5^(2*(3^k)) - 5^(3^k) + 1)

Here, we have factored the expression using the identity a^3 + b^3 = (a + b)(a^2 - ab + b^2).

Now, let's focus on the second factor, (5^(2*(3^k)) - 5^(3^k) + 1).
Note that the first term, 5^(2*(3^k)), is divisible by 9 since 2*(3^k) is greater than or equal to 2, making it a multiple of 2, and hence divisible by 3 twice.

The second term, -5^(3^k), is divisible by 3^(k+1) based on our assumption that it holds true for k.

The last term, 1, is obviously divisible by any power of 3.

Therefore, we can conclude that the entire expression (5^(3^k))^3 + 1 is divisible by 3^(k + 2), based on the fact that each factor in the expression is divisible by 3^(k + 2).

Now, we have proven that if the statement holds true for k, then it also holds true for k + 1.

Since the base case has been established, and the step of induction has been proven, we can conclude that the statement is true for all non-negative integers n.

Hence, we have shown that 5^(3^n) + 1 is divisible by 3^(n + 1) for all non-negative integers n.