$a^n+\frac {1}{a^n} =(a+\frac {1}{a})(a^{n-1}+\frac {1}{a^{n-1}})-(a^{n-2}+\frac {1}{a^{n-2}})$

Trivial by Strong form of induction. Let us assume that $a^i+\frac{1}{a^i}$ is an integer for all $i \in {1,2,....n-1}$ Now, $a^n+\frac{1}{a^n}=(a+\frac{1}{a})(a^{n-1}+\frac{1}{a^{n-1}})-({a^{n-2}}+\frac{1}{a^{n-2}})$ The RHS is an integer by assumption forcing the L.H.S to be an integer

This problem can also be solved by paying attention that the expression $x^n+y^n$ is expressible in terms of $x+y$ and $xy$ in the form of a two variable polynomial with integer coefficients, here , $ x=a , y =1/a $ and since $ x+y=a+\frac{1}{a}$ and $xy=a.\frac{1}{a}=1$ are integers, we are done.

SohamSchwarz119 wrote: Trivial by Strong form of induction. Let us assume that $a^i+\frac{1}{a^i}$ is an integer for all $i \in {1,2,....n-1}$ Now, $a^n+\frac{1}{a^n}=(a+\frac{1}{a})(a^{n-1}+\frac{1}{a^{n-1}})-({a^{n-2}}+\frac{1}{a^{n-2}})$ The RHS is an integer by assumption forcing the L.H.S to be an integer I believe there is one thing wrong with your proof: you never mentioned any base case. SOLUTION: We use induction. BASE CASE: $n=1,2$ When $n=0$, $a^n+\frac{1}{a^n}$ is an integer, so it does work when $n=1$. Similarly, if $n=2$, $a^2+\frac{1}{a^2} = \left(a+\frac{1}{a} \right)^2-2$, which is indeed an integer. INDUCTIVE STEP: Note that $a^n+\frac{1}{a^n} = \left(a+\frac {1}{a}\right) \left(a^{n-1}+\frac {1}{a^{n-1}} \right)- \left(a^{n-2}+\frac {1}{a^{n-2}} \right)$, so if $a^{n-1}+\frac{1}{a^{n-1}}$ and $a^{n-2}+\frac{1}{a^{n-2}}$ are integers, $a^{n}+\frac{1}{a^{n}}$ is too.

AopsUser101 wrote: SohamSchwarz119 wrote: Trivial by Strong form of induction. Let us assume that $a^i+\frac{1}{a^i}$ is an integer for all $i \in {1,2,....n-1}$ Now, $a^n+\frac{1}{a^n}=(a+\frac{1}{a})(a^{n-1}+\frac{1}{a^{n-1}})-({a^{n-2}}+\frac{1}{a^{n-2}})$ The RHS is an integer by assumption forcing the L.H.S to be an integer I believe there are several things wrong with your proof. Firstly, you never mentioned any base case. Secondly, this isn't exactly strong induction because we don't assume validity for all preceding terms, just the preceding two. Sure, you can solve using strong induction, but I think you can get tighter than this. SOLUTION: We use induction. BASE CASE: $n=1,2$ When $n=0$, $a^n+\frac{1}{a^n}$ is an integer, so it does work when $n=1$. Similarly, if $n=2$, $a^2+\frac{1}{a^2} = \left(a+\frac{1}{a} \right)^2-2$, which is indeed an integer. INDUCTIVE STEP: Note that $a^n+\frac{1}{a^n} = \left(a+\frac {1}{a}\right) \left(a^{n-1}+\frac {1}{a^{n-1}} \right)- \left(a^{n-2}+\frac {1}{a^{n-2}} \right)$, so if $a^{n-1}+\frac{1}{a^{n-1}}$ and $a^{n-2}+\frac{1}{a^{n-2}}$ are integers, $a^{n}+\frac{1}{a^{n}}$ is too. This is still considered strong induction.

Let's break this down into 2 parts. 1. Let's assume that n is even. n=2k for some positive integer k. Claim:$$(a+1/a)^{2k} \in \mathbb{Z} \Rightarrow (a+1/a)^{2k+2} \in \mathbb{Z} $$ Proof:$$(a\hspace{1mm}+\hspace{1mm}1/a)^{2k+2}=a^{2k+2}\hspace{1mm}+\hspace{1mm}1/a^{2k+2}+\binom{2k+2}{1}(a^{2k+1}\hspace{1mm}\cdot\hspace{1mm}1/a^{1})+\binom{2k+2}{2k+1}(a^{1}\hspace{1mm}\cdot\hspace{1mm}1/a^{2k+1})+...+\binom{2k+2}{k}(a^{k+2}\hspace{1mm}\cdot\hspace{1mm}1/a^{k})+\binom{2k+2}{k+2}(a^{k}\hspace{1mm}\cdot\hspace{1mm}1/a^{k+2})+\binom{2k+2}{k+1}(a^{k+1}\hspace{1mm}\cdot\hspace{1mm}1/a^{k+1})\hspace{2mm}(m)$$ $$\binom{2k+2}{1}(a^{2k+1}\hspace{1mm}\cdot\hspace{1mm}1/a^{1})+\binom{2k+2}{2k+1}(a^{1}\hspace{1mm}\cdot\hspace{1mm}1/a^{2k+1})=\binom{2k+2}{1}(a^{2k}+1/a^{2k})\hspace{2mm}(1)$$$$\binom{2k+2}{2}(a^{2k}\hspace{1mm}\cdot\hspace{1mm}1/a^{2})+\binom{2k+2}{2k}(a^{2}\hspace{1mm}\cdot\hspace{1mm}1/a^{2k})=\binom{2k+2}{2}(a^{2k-2}+1/a^{2k-2})\hspace{2mm}(2)$$$$\binom{2k+2}{k}(a^{k+2}\hspace{1mm}\cdot\hspace{1mm}1/a^{k})+\binom{2k+2}{k+2}(a^{k}\hspace{1mm}\cdot\hspace{1mm}1/a^{k+2})=\binom{2k+2}{k}(a^{2}+1/a^{2})\hspace{2mm}(k+1)$$$$\binom{2k+2}{k+1}(a^{k+1}\hspace{1mm}\cdot\hspace{1mm}1/a^{k+1})=\binom{2k+2}{k+1}(k+2)$$$$(1)+(2)+....+(k+1)+(k+2)=(m)$$ This case is true,because $$a^2+1/a^2=(a+1/a)^2-2\in \mathbb{Z}$$ 2.What if n=2k+1 for some k natural number? $$(a^{2k+1}+1/a^{2k+1})=(a+1/a)(a^{2k}-a^{2k-2}+a^{2k-4}-...+1/a^{2k})$$$$a\hspace{1mm}+\hspace{1mm}1/a\in \mathbb{Z}\hspace{10mm}a^{2k}-a^{2k-2}+a^{2k-4}-...+1/a^{2k}\in \mathbb{Z}\Rightarrow (a^{2k+1}\hspace{1mm}+\hspace{1mm}1/a^{2k+1})\in \mathbb{Z} $$