Prove by induction that a^n+a^-n is an integer.

Question

I am to prove by induction that given that $a+1/a$ is an integer (i.e. belongs to Z ) then $a^n+1/a^n$ is an integer too. I'm pretty much clueless here. Thanks in advance.

Answer 1

HINT:

$$\begin{align*} \left(a^n+\frac1{a^n}\right)\left(a+\frac1a\right)&=a^{n+1}+a^{n-1}+\frac1{a^{n-1}}+\frac1{a^{n+1}}\\\\ &=\left(a^{n+1}+\frac1{a^{n+1}}\right)+\left(a^{n-1}+\frac1{a^{n-1}}\right)\;, \end{align*}$$

so

$$a^{n+1}+\frac1{a^{n+1}}=\left(a^n+\frac1{a^n}\right)\left(a+\frac1a\right)-\left(a^{n-1}+\frac1{a^{n-1}}\right)\;.$$

Answer 2

HINT:

We need Strong induction here

Use $$\left(a^n+\frac1{a^n}\right)\left(a+\frac1a\right)=\left(a^{n+1}+\frac1{a^{n+1}}\right)+\left(a^{n-1}+\frac1{a^{n-1}}\right)$$

$$\implies \left(a^{n+1}+\frac1{a^{n+1}}\right)=\left(a^n+\frac1{a^n}\right)\left(a+\frac1a\right)-\left(a^{n-1}+\frac1{a^{n-1}}\right)$$

Assume $\displaystyle a^{n-1}+\frac1{a^{n-1}},a^n+\frac1{a^n}$ are integers

Base cases $$a^2+\frac1{a^2}=\left(a+\frac1a\right)^2-2$$

and $$a^3+\frac1{a^3}=\left(a+\frac1a\right)^3-3\left(a+\frac1a\right)$$