Lesson in an induction problem 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.
 A: 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$$
A: 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!
