Can somebody help me with these questions? I can't seem to get started...
Having $P(n) : n^2 + 5n + 1\text{ is even}$.
a) Demonstrate that if $P(k)$ is True to some $k$ natural, then $P(k + 1)$ is also true.
b) Considering the Principle of Complete Induction, can you say that $P(n)$ is true for all natural numbers?
c) Demonstrate that $P(n)$ is False for all n natural.
Thank you!
a) Let $P(n)$ be the assertion that $n^2+5n+1$ is even. We show that if $P(k)$ is true for a particular $k$, then $P(k+1)$ is true.
Suppose that $k^2+5k+1$ is even. Note that $$(k+1)^2+5(k+1)+1=k^2+2k+1+5k+5+1=(k^2+5k+1)+(2k+6).\tag{1}$$ By the induction assumption, $k^2+5k+1$ is even. But $2k+6$ is even, and if we add an even number to an even number, the result is even. This completes the proof of the induction step.
b) The Principle of Mathematical Induction says that if (i) $P(1)$ is true and (ii) whenever $P(k)$ is true, $P(k+1)$ is true, then $P(n)$ is true for all $n\ge 1$.
We have proved (ii). But we must also verify (i). And notice that when $n=1$, we have $n^2+5n+1=7$, and $7$ is odd. So (i) fails, and therefore the induction "proof" fails.
c) We will show that in fact $n^2+5n+1$ is odd for all $n\ge 1$. Let $P^\ast(n)$ be the assertion that $n^2+5n+1$ is odd.
It is easy to verify that $P^\ast(1)$ is true, we just verified it above.
Now let us show that if $P^\ast(k)$ holds, then $P^\ast(k+1)$ holds. We use the calculation in (1). There we concluded that $$(k+1)^2+5(k+1)+1=(k^2+5k+1)+(2k+6).$$ By the induction assumption, $k^2+5k+1$ is odd. But $2k+6$ is even, and an odd plus an even is odd, so $(k+1)^2+5(k+1)+1$ is odd. This completes the proof of the induction step.
Remark: Basically the only point of this exercise is to remind you that in an induction argument, you must show two things: that $P(1)$ holds, and that whenever $P(k)$ holds, $P(k+1)$ must hold. I actally don't quite see the point, since students almost never forget to verify that $P(1)$ holds.
1) Assume $P(k)$ is even. Now, for $P(k+1)$, we have $$\begin{align} \ P(k+1) &=(k+1)^2+5(k+1)+1 \\ &=k^2+2k+1+5k+5+1 \\ &=k^2+5k+1+2k+5+1 \\ &=2m+2k+6 \text{ (why?)} \\ &=2(m+k+3) \end{align}$$ Thus $P(k+1)$ is even.
However, for #3, $$n^2+5n=n(n+5)$$ And since $n$ and $n+5$ are of different parity, $n^2+5n$ is even which means it can be represented as $2p$ for some integer $p$ Thus, $$n^2+5n+1=2p+1$$ What does that mean??
I left the complete induction for you...
First, if you let n = 1 then you get P(n) = 7 which is not even. So you are never going to show it is true for all natural numbers. If it were true that if P(n) is even for some n, then yes P(n+1) would be even. To see that P(n+1) = (n+1)2 +5(n+1) + 1 =$n^2$ +2n + 1 + 5n + 5 + 1 = ($n^2$ + 5n + 1) + (2n + 6). We assumed first term is even, and clearly the second term is.
But if you assume P(n) is odd for some n, then the above analysis shows that P(n+1) is also odd. So this demonstrates P(n) is odd for n ≥ 1, which includes all the natural numbers.
You need a starting point and the induction argument to get the induction going. But hey:
$$n_2+5n+1=n(n+1)+4n+1.$$
Now $n(n+1)$ is even because it's a product of an odd number and an even number, and obviously $4n$ is even making the whole thing odd.
