Induction problem 4


The claim looks like something where you can do the inductive step using the true of the claim at the immediately previous value of n. Sadly, this is wrong. You'll need to use the fact that the claim is true at two previous values of n.

Try multiplying out the product \((\displaystyle x + \frac{1}{x}) (\displaystyle x^k + \frac{1}{x^k})\). Don't ask why. Just try doing it and look at what you have. Try to relate parts of the resulting formula to the formulas in (a) the goal of your inductive step and (b) what you can get from the inductive hypothesis.