# Thread: Prove using induction

1. ## Prove using induction

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

2. ## Re: Prove using induction

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

3. ## Re: Prove using induction

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

$\displaystyle =a_n(a_n-1)$

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

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

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

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

4. ## Re: Prove using induction

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

$\displaystyle =a_n(a_n-1)$

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

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

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

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

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

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

5. ## Re: Prove using induction

I just got it!!

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

$\displaystyle 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.

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

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

$\displaystyle =a_n^4-a_n^2$

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

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

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

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