Mathematical Induction: Can I assume that $P(k-1)$ is also true in the induction hypothesis?

Question

Suppose that $y \in \mathbb{R}$, $y \neq 0$ and $y + \frac{1}{y} \in \mathbb{Z}$. Prove using mathematical induction that $y^{n} + \frac{1}{y^{n}}$ is an integer for all $n \geq 1$.

Basis step: The statement is true for $n=1$ since: $y^{1} + \frac{1}{y^{1}} = y^{n} + \frac{1}{y^{n}} \in \mathbb{Z}$.

Induction hypothesis: Assume that $y^{k} + \frac{1}{y^{k}}$ and $y^{k-1} + \frac{1}{y^{k-1}}$ are integers for all $n \geq 1$.

Induction step: We show that $y^{k+1} + \frac{1}{y^{k+1}}$ is true.

$y^{k+1} + \frac{1}{y^{k+1}} = (y^{k} + \frac{1}{y^{k}})(y + \frac{1}{y}) - (\frac{y^{k}}{y} + \frac{y}{y^{k}})$

$y^{k+1} + \frac{1}{y^{k+1}} = (y^{k} + \frac{1}{y^{k}})(y + \frac{1}{y}) - (y^{k-1} + \frac{1}{y^{k-1}})$

Since it is given that $y + \frac{1}{y} \in \mathbb{Z}$ and by the induction hypothesis, $y^{k} + \frac{1}{y^{k}}$, $y^{k-1} + \frac{1}{y^{k-1}} \in \mathbb{Z}$:

$\Rightarrow (\mathbb{Z})(\mathbb{Z})-\mathbb{Z}=\mathbb{Z}$ (Closure property for integers)

Therefore, $y^{n} + \frac{1}{y^{n}}$ is an integer for all $n \geq 1$.

This is the only way I was able to do the proof. However, I want to know if I am allowed to assume that $P(k-1)$ is also true in the induction hypothesis since as far as I know we can only assume that $P(k)$ is true. Would also appreciate feedback and alternative solutions for my proof!

Answer 1

You don't actually require strong induction, and strong induction on the statement "$y^{n} + \frac{1}{y^{n}}$ is an integer" requires a little more than you were able to show.

The problem lies in establishing $P(2)$. If you only have $P(1),$ and your inductive step requires two previous cases, you are stuck. Strong induction is not a get-out-of-jail-free card you can play in this situation; if it were, a lot of nonsensical "fake proofs" would actually be provable.

What I think you actually need here is just a "bigger statement". Instead of saying $P(n)$ is "$y^{n} + \frac{1}{y^{n}}$ is an integer", say that $P(n)$ is "$y^{n} + \frac{1}{y^{n}}$ is an integer and $y^{n+1} + \frac{1}{y^{n+1}}$ is an integer." Then in order to do the inductive step, that is, to show that $P(n)$ implies $P(n+1)$, write $P(n+1)$. It is

$$ y^{n+1} + \frac{1}{y^{n+1}} \text{ is an integer and } y^{n+2} + \frac{1}{y^{n+2}} \text{ is an integer.} $$

The first half ($y^{n+1} + \frac{1}{y^{n+1}}$ is an integer) is easy, because $A \land B \implies B$ and in this proof $P(n)$ is of the form $A \land B$ where $B$ is "$y^{n+1} + \frac{1}{y^{n+1}}$ is an integer."

And the inductive step you already found proves the second half ($y^{n+2} + \frac{1}{y^{n+2}}$ is an integer).

Now to get started, you just need to fill in a base case. But you need two parts to this base case; $y + \frac1y$ is only half of a suitable base case. To complete the base case, you could prove that $y^2 + \frac{1}{y^2}$ is an integer (where you're allowed to use the fact that $y + \frac1y$ is an integer; just remember this is part of proving the base case, not an inductive step).

Another way to get a complete base case would be to prove that $y^0 + \frac{1}{y^0}$ is an integer. That is, your base case would be $P(0).$ I think this should be easy enough to prove; in fact you can even show which integer $y^0 + \frac{1}{y^0}$ is.

---

A way to do it that actually does use strong induction and just the statement for $y + \frac1y$ as a base case is to separate your inductive step into two cases. One case applies when $k + 1 = 2$; in this case you must prove $P(2)$ using only $P(1).$ The other case applies when $k + 1 > 2$; then, since $k - 1 \geq 1,$ you know $P(k-1)$ is one of the statements $P(1),P(2),\ldots,P(k),$ so by strong induction you get to assume it for the inductive step. To make your proof use this method you would have to say you are invoking strong induction, and you would have to work out the case $k+1=2.$

Answer 2

For $n=2$ and $n=1$ the statement is correct.

Because, $$\left(y^2+\frac{1}{y^2}\right)=\left(y+\frac 1y\right)^2-2$$

Then ,suppose that $n=k$ and $n=k-1$ are also correct.....

Answer 3

Yes, that is "strong induction", and it follows from induction.

Strong induction:

$$P(0)\land(\forall n: (\forall k: k\leq n \Rightarrow P(k))\Rightarrow P(n+1))\Rightarrow\forall n :P(n)$$

Answer 4

Here's a way you can see it. Suppose $n$ is a counterexample, so that $y^n+\frac{1}{y^n} \notin \Bbb Z$ for some $n$. Then because every non-empty set of natural numbers has a least element, there must be some least $n$ that works as a counterexample. Therefore, for each $k \lt n, y^k+\frac{1}{y^k} \in \Bbb Z$. Moreover, $n \neq 1, 2$. From here, use your proof.