Mathematical Induction proof for a cubic equation.

Question

If $ x^3 = x +1$, prove by induction that $ x^{3n} = a_{n}x + b_n + \frac {c_n}{x}$, where $a_1=1, b_1=1, c_1=0$ and $a_n = a_{n-1} + b_{n-1}, b_n = a_{n-1} + b_{n-1} + c_{n-1}, c_n = a_{n-1} + c_{n-1}$ for $n=2,3,\dots $

For $n=1$ we have $x_3 = a_1x + b_1 + \frac {c_1}{x}$ = x + 1 + $\frac{0}{x}$ = x + 1, which is true.

Assume the case for $n=k$ is true, so $x^{3k} = a_kx + b_k + \frac{c_k}{x}$

So for $n = k+1$ (and using $a_n = a_{n-1} + b_{n-1}, b_n = a_{n-1} + b_{n-1} + c_{n-1}, c_n = a_{n-1} + c_{n-1}$ for $n=2,3,...), $ we have:

$ \begin{align} x^{3(k+1)} &= (a_{k+1-1}x + b_{k+1-1}){x} + (a_{k+1-1} + b_{k+1-1} + c_{k+1-1}) + ( \frac{(a_{k+1-1} + c_{k+1-1})}{x}) \\ &= (a_k + b_k){x} + ( a_k + b_k + c_k) + \frac{(a_k + c_k)}{x} \\ &= a_{k+1}{x} + b_{k+1} + \frac{c_{k+1}}{x} \\\end{align} $

This is the same form as $ x^{3k} $ but for n=k+1. Therefore, if the result is true for k, it is also true for (k+1).

Would you proceed like this or would you add the $(k+1)$th term and show that it is equal to the $k$th term with $n$ (or $k$) replaced by $k+1$?

Answer 1

Hint: Multiply $x^{3n} = a_{n}x + b_n + \frac {c_n}{x}$ on the left by $x^3$ and on the right by $x+1$. Regroup and deduce a formula for $a_{n+1}$, $b_{n+1}$, $c_{n+1}$ in terms of $a_{n}$, $b_{n}$, $c_{n}$.

Answer 2

The basic idea is that $x^3=x+1$ implies

$$x^2=1+{1\over x}\quad\text{and}\quad x^4=x^2+x=1+{1\over x}+x$$

So if $x^{3k}=a_kx+b_k+{c_k\over x}$ then

$$\begin{align} x^{3(k+1)}&=x^3\cdot x^{3k}\\ &=x^3(a_kx+b_k+{c_k\over x})\\ &=a_kx^4+b_kx^3+c_kx^2\\ \end{align}$$

Now replace the $x^4$, $x^3$, and $x^2$ in the last line with $1+{1\over x}+x$, $x+1$, and $1+{1\over x}$, respectively, simplify, and voila.

Answer 3

You should put "$=$" between things ALREADY KNOWN to be equal, not with things you are trying to prove to be equal. You should not start a chain of equalities with the very equality you're trying to prove.

Thus \begin{align} x^{3(k+1)} & = x^3 x^{3k} & & \text{(This known, by routine algebra.)} \\[10pt] & = x^3 ( a_kx + b_k + c_k x^{-1} ) & & \text{(This comes from the induction hypothesis.)} \\[10pt] & = (x+1)( a_kx + b_k + c_k x^{-1} ) & & \text{(This is true by hypothesis.)} \\[10pt] & = a_k x^2 + (a_k+b_k)x + (c_k+b_k) + c_k x^{-1} & & \text{(true by routine algebra)} \\[10pt] & = \frac{a_k x^3} x + (a_k+b_k)x + (c_k+b_k) + c_k x^{-1} & & \text{(ditto)} \\[10pt] & = \frac{a_k (x+1)} x + (a_k+b_k)x + (c_k+b_k) + c_k x^{-1} & & \text{(by hypothesis)} \\[10pt] & = (a_k+b_k)x + (a_k + c_k+b_k) + (a_k+c_k) x^{-1} & & \text{(routine algebra again)} \end{align}