0

This is a question from An Invitation to Combinatorics. The question is as follow:

A specific statement about the positive integer n is denoted by P(n). We can prove that, whenever P(k) is true, then P(k + 1) is also true. It is also known that P(47) is false. Given only this information, what is the strongest conclusion that follows?

Give this information, I have arrived at the conclusion that P(i) is false for $i > 45$. The reason being that if $P(47)$ is false, then we can't show $P(48)$. And this chain of reasoning continues. Is this answer correct?

Parth Patel
  • 3

2 Answers2

1

If $P(47)$ is false, it means we cannot use the implication $P(k) \implies P(k+1)$ to prove $P(48)$. However, it doesn't mean that $P(48)$ is false.

However, notice that the contrapositive of $P(k) \implies P(k+1)$ is $\lnot P(k) \impliedby \lnot P(k+1)$ or in other words $\lnot P(k) \implies \lnot P(k-1)$. So from $P(47)$ being false we can imply that $P(46)$ is false, and from $P(46)$ being false we imply that $P(45)$ is false, so so forth for all integers $k \leq 47$.

As an example of a statement which demonstrates this property, consider $P(k) := (k \geq 48)$. Notice that in fact $P(k)$ is true for $k \geq 48$ and false for $k \leq 47$.

ConMan
  • 24,300
0

If P(47) is false then P(46) must be false. And if P(46) is false P(45) must be also false. So P(i) is false for $i \leq 47$

abc
  • 497