Lesson in an induction problem

Question

I'm trying to do this problem but I'm having a basic misunderstanding that just needs some clarification.

Consider the proposition that $P(n) = n^2 + 5n + 1$ is even.

Prove $P(k) \to P(k+1)$ $\forall k \in \mathbb N$.

For which values is this actually true?

What is the moral here?

This problem is meant to tell you a moral problem of induction. I'm aware that $P(n)$ is odd for all integers (I think), so I can't think of where to start on this. This is in regard to induction specifically even if the problem doesn't implicitly state it.

Answer 1

You should be doing the base case before the inductive step. It can be shown that $n=k+1$ follows from $n=k$ using just the inductive step, however that does not imply that the proposition is true.

---

Here I demonstrate this:

Assume true for $n=k$ where $p\in \mathbb{Z}$: $$k^2+5k+1=2p$$ For $n=k+1$: $$(k+1)^2+5(k+1)+1=k^2+2k+1+5k+5+1=(k^2+5k+1)+2k+6$$ Substituting gives: $$2p+2k+6$$ Hence, this implies that $n=k+1$ follows from $n=k$.

---

However, note that when we do the base case, $n=1$, we see that this proposition is not true: $$1^2+5+1=7$$

Answer 2

While you can prove the step that $P(k) \rightarrow P(k+1)$ for all $k \in \mathbb{N}$, it does not follow that "$n^2+5n+1$ is even" for all $n \in \mathbb{N}$.

In other words, the moral is to never forget to prove the base case for induction, for otherwise you might be proving things that are just not true.

Here is a simpler example:

Suppose I want to use induction to prove $P(n): n > n + 1$ for all $n \in \mathbb{N}$

OK, so take arbitrary $k \in \mathbb{N}$, and suppose (inductive hypothesis) that $k > k + 1$. Well, then obviously $k + 1 > (k + 1) + 1$, and so the inductive step is proven. So there!

But wait! Clearly $n > n + 1$ is not true! What happened? I forgot the base case!