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} = \left( x+x^{-1} \right)^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

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

From here

$$ x^{k+1} + x^{-(k+1)} = \left( x^{k}+x^{-k} \right) \left( x+x^{-1} \right) – 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}$.

---