Question on Mathematical Induction Logic

Question

The following is from a Discrete Mathematics textbook on induction:

Suppose that, for some predicate $P(k)$, you first prove that $P(1)$ is true, and then you do the following. You prove that, for every positive even integer $k$, if $P(i)$ is true for all odd integers $i$ such that $0 < i < k$, then $P(k+1)$ is true. For which values of $n$ can you now be certain that $P(n)$ is true?

My intuition is to say the following:

• We know that $n=1$ must be true.
• Since $1$ is odd, we proved that $P(k+1)$ is true where $k$ is even; but since $k$ is even, then $k+1$ is odd, thus proving all odd integers once more...
• So it seems we can only say $P(n)$ is true $\forall n \in Odds$

However I am unsure of why the fact that $0 < i < k$ is necessary in the problem... possibly I am misunderstanding the problem, or is this just useless information in the context of this problem?

I am not looking for an answer, rather a hint or suggestion. Thanks.

Answer 1

Your intuition is correct, but your justification is at best very unclear. Let’s first show that we really can be sure that $P(n)$ is true for all odd $n$. Specifically, let’s prove by complete induction on $k$ that $P(2k+1)$ is true for each non-negative integer $k$.

First, $P(2\cdot0+1)=P(1)$, which we’re told is true; that takes care of the basis step.

Now suppose that $k>0$, and $P(2\ell+1)$ is true for each non-negative integer $\ell<k$. The numbers $2\ell-1$ for $0\le\ell<k$ are $1,3,\ldots,2(k-1)+1=2k-1$; these are the odd numbers $i$ such that $0<i<2k$, and $2k$ is even, so we’re told that $P(2k+1)$ is true. This takes care of the induction step and establishes that $P(2n+1)$ is true for all non-negative integers $n$, i.e., for all odd positive integers.

To see that we cannot conclude anything about $P(n)$ when $n$ is even, observe that the information that we were given tells us about the truth of $P(n)$ only when $n=1$ or $n=k+1$ for some even $k$, and in both of these cases $n$ is odd. The information therefore gives us no way to conclude that $P(n)$ is true for any even $n$. Thus, the values of $n$ for which we can be sure that $P(n)$ is true are precisely the odd positive integers.

---

The problem does not assert that $0<i<k$. It simply says, as part of the information available to you, that if you know that $P(i)$ is true for all odd integers $i$ such that $0<i<k$, then you can conclude that $P(k+1)$ is also true. There’s no point questioning this: it’s simply part of the information that you’ve been given. The problem could have given different information that would still have allowed you to draw the same conclusion:

Suppose that, for some predicate $P(k)$, you first prove that $P(1)$ is true, and then you do the following. You prove that, for every positive even integer $k$, if $P(k-1)$ is true, then $P(k+1)$ is true. For which values of nn can you now be certain that $P(n)$ is true?

Had the question been formulated this way, you could have used an ordinary induction on $k$ (instead of a complete induction) to show that $P(2k+1)$ is true for each non-negative integer $k$.

Answer 2

The $0 < i < k$ is part of the inductive step. You prove $P(k+1)$ using the fact that you know $P(i)$ is true for $0 < i < k$, the cases you've checked or inductively assumed to be true.

If you already knew $P(i)$ for all odd $i$, then you wouldn't need to show $P(k+1)$ is true. You'd already have it since $k+1$ is odd and the problem wouldn't require induction at all.