2

For each $n \in \mathbb{N}$ we have a statement $P(n)$. We know that the following statements are true:

$$P(0) \tag1$$

$$P(1)\tag 2$$

$$\forall n\in \mathbb{N} (P(n)\text{ and }P(n+1)) \to P(n+2) \tag3$$

I'm to show that $\forall k\in \mathbb{N}$ $P(k)$ must be true.

I've encountered induction proofs before, but I'm a little bit uncertain about how to proceed here. I'm thinking:

$P(0)$ is true. And then we have our induction hypothesis (IH): $P(k)$ is true. Then I have to show that $P(k+1)$ is true. By using (3) with $P(0)$ and $P(1)$, I get that $P(2)$ is true. And by using (3) with $P(1)$ and $P(2)$ I get that $P(3)$ is true and so on.

$\bigg($by using (3) for i= 0 to i = k-3 I then get $P(i)$ is true, $\forall i\in [0,k-1]$ and then using (3) again with $n=k-1$ I get that $P(k+1)$ is true. $\bigg)$

But I feel like this is a pretty lousy induction proof and not how I'm supposed to do it.

Arthur
  • 199,419
Mathaniel
  • 781

1 Answers1

2

Hint:

Define $Q(n)$ as $Q(n) = P(n)\land P(n+1)$ and prove that $Q(n)$ is true by induction.

5xum
  • 123,496
  • 6
  • 128
  • 204
  • So something like this: IH: $Q(n)$. $Q(0) = P(0)∧P(0+1)$ [is true by (1) and (2)]. To show: $Q(n+1)$. $Q(n+1) = P(n+1) ∧ P(n+2)$ Since we've assumed that $Q(n)$ is true $\to P(n) ∧ P(n+1)$ is true $\to P(n+2)$ is true $\to P(n+1) ∧ P(n+2) = Q(n+1)$ is true ? – Mathaniel Oct 03 '17 at 12:19
  • @Mathaniel $Q(0)$ is not $P(0)\land P(n+1)$. It is $(P(0)\land P(1)$. – 5xum Oct 03 '17 at 12:20
  • Yeah, I know, I made a typo and have corrected it. Is the rest ok? – Mathaniel Oct 03 '17 at 12:21
  • @Mathaniel The rest looks OK, but I suggest you write it down and write the reason why you can make each step more clearly. – 5xum Oct 03 '17 at 12:21
  • Thanks, I will :) This was just a rough draft. – Mathaniel Oct 03 '17 at 12:23