0

Prove:

Let $t$ be a fixed integer and $j$ a fixed positive integer.

Show that if $P(t), P(t+1),\dotsc,P(t+j)$ are true and $[P(t)\land P(t+ 1) \land \dotsb \land P(k)]\implies P(k+1)$ is true for every integer $k \ge t$, then $P(n)$ is true for all integers $n$ with $n \ge t$.

I'm pretty lost on this. I suspected that contrapositive might be the easiest way to show this but I'm not sure how to do it.

Community
  • 1
kowitzha
  • 11

1 Answers1

1

Suppose the statement is false, and let $n_0 \ge t$ be least such that $P(n_0)$ fails. (We must have $n_0 > t+j$, but this is kind of irrelevant.)

You know that $P(t) \wedge P(t+1) \wedge \cdots \wedge P(n_0-1)$ holds by minimality of $n_0$, and hence $P(n_0)$ holds by the given condition, contradicting your assumption that $P(n_0)$ fails.

Clive Newstead
  • 64,925
  • Thanks a lot, that really helps. Out of curiosity, how would you prove it by strong induction directly? I think that's the direction we were intended supposed to go in. – kowitzha Dec 03 '13 at 04:27
  • induction, well-ordering, these are axioms. They are logically equivalent. We must start somewhere. –  Dec 03 '13 at 05:36
  • @kowitzha: What I did was prove your statement from the well-ordering principle. You can prove strong induction in exactly the same way -- this is why I said the $j$ is irrelevant: omitting all that stuff and just requiring that $P(t)$ holds (i.e. for $j=0$) is exactly the statement of strong induction. – Clive Newstead Dec 03 '13 at 15:39
  • But doesn't the formal statement of strong induction say that it has to start at 1 rather than at some t? What would the actual direct proof using strong induction with a base case and inductive step actually look like? It looks pretty much trivial to me, like there is really nothing to show. – kowitzha Dec 03 '13 at 15:55
  • @kowitzha: If your strong induction principle starts at $1$ then just replace $t$ by $1$ in the proof. – Clive Newstead Dec 03 '13 at 16:49
  • How can we rigorously justify doing that? – kowitzha Dec 03 '13 at 16:55
  • By writing the proof out. – Clive Newstead Dec 03 '13 at 16:57