1. ## Prove using induction

Let $a_1=5$, and let $a_{n+1}=a_n^2$. Prove that the last n digits of $a_n$ are the same as the last n digits of $a_{n+1}$.

2. ## Re: Prove using induction

Find the general term for the sequence, factorize the difference $a_{n+1} - a_n$ using the formula $x^2 - y^2 = (x+y)(x-y)$ and show that $10^n$ divides it.

3. ## Re: Prove using induction

Originally Posted by Traveller
Find the general term for the sequence, factorize the difference $a_{n+1} - a_n$ using the formula $x^2 - y^2 = (x+y)(x-y)$ and show that $10^n$ divides it.
$a_{n+1}-a_n=a_n^2-a_n$

$=a_n(a_n-1)$

$=5^{2^{n-1}}(5^{2^{n-1}}-1)$

Since $2^{n-1} \geq n$,

$5^n | 5^{2^{n-1}}(5^{2^{n-1}}-1)$

How do I show that $2^n | (5^{2^{n-1}}-1)$?

4. ## Re: Prove using induction

Originally Posted by alexmahone
$a_{n+1}-a_n=a_n^2-a_n$

$=a_n(a_n-1)$

$=5^{2^{n-1}}(5^{2^{n-1}}-1)$

Since $2^{n-1} \geq n$,

$5^n | 5^{2^{n-1}}(5^{2^{n-1}}-1)$

How do I show that $2^n | (5^{2^{n-1}}-1)$?
You may be familiar with the result that says: If $a$ is odd, then $2^{n+2}|a^{2^n}-1$ for $n\geq1$.

The main part of the proof by induction on $n$ is:
Suppose for some $n\geq1$ it's true that $2^{n+2}|a^{2^n}-1$. Then look at $a^{2^{n+1}}-1=(a^{2^n}-1)(a^{2^n}+1)$.

In particular, $2^{n+1}|5^{2^{n-1}}-1$ and therefore $2^n|5^{2^{n-1}}-1$.

5. ## Re: Prove using induction

I just got it!!

We need to prove that $a_{n+1}-a_n$ is divisible by $10^n$.

$a_2-a_1=25-5=20$, which is divisible by 10.

So, the statement is true for n = 1.

Let the statement be true for n.

$a_{n+1}-a_n=a_n^2-a_n$ is divisible by $10^n$.

$a_{n+2}-a_{n+1}=a_{n+1}^2-a_{n+1}$

$=a_n^4-a_n^2$

$=(a_n^2-a_n)(a_n^2+a_n)$

$a_n^2-a_n$ is divisible by $10^n$.

$a_n^2+a_n=a_{n+1}+a_n$ is divisible by 10. (As both $a_{n+1}$ and $a_n$ end with 5.)

So, $(a_n^2-a_n)(a_n^2+a_n)=a_{n+2}-a_{n+1}$ is divisible by $10^{n+1}$. This completes the proof.