Mathematical Induction proof for a cubic equation. 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$?
 A: 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}
A: 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.
A: 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}$.
