Mathematical Induction: Algebra

Mathematical Induction is used to prove that the statement of the problem is true for all natural numbers $n$. Mathematical Induction consists of proving the following three theorems.

Theorem 1 (Base of Induction): The statement of the problem is true for $n=1$.

Theorem 2 (Inductive Step): If the statement is true for some $n=k$, then it must also be true for $n=k+1$.

Theorem 3 (Peano Axiom): If Theorems 1 and 2 hold, then the statement of the problem is true for all natural numbers $n$.

 

Problem (Germany, 1995)

Let $x$ be a real number, such that $x+x^{-1}$ is an integer. Show that $x^n+x^{-n}$ is also an integer for all $n\in \mathbb{N}$.

Solution

Theorem 1 (Base of Induction): The statement is obviously true for $n=1$. The statement is also true for $n=2$, since

$$x^2+x^{-2}={(x+x^{-1})}^2–2$$

Theorem 2 (Inductive Step): Let us assume that the statement holds for $n=k-1$ and $n=k$, i.e. that $x^{k-1}+x^{-(k-1)}$ and $x^k+x^{-k}$ are integers.

 

Let us consider the expression

$$(x^k+x^{-k})(x+x^{-1})=x^{k+1}+x^{-(k+1)}+x^{k-1}+x^{-(k-1)}$$

From here

$$x^{k+1}+x^{-(k+1)}=(x^k+x^{-k})(x+x^{-1})–x^{k-1}–x^{-(k-1)}-$$

is an integer number and the statement holds for $n=k+1$.

Theorem 3 (Peano Axiom): Since Theorems 1 and 2 hold, then the statement of the problem is true for all $n\in \mathbb{N}$.

---