Translating a strong induction to test cases if valid or invalid? answers given

[mr_coffee]

Hello everyone.

I"m trying to break down this problem, the answers are given I just want to make sure I'm understanding it right.

http://img204.imageshack.us/img204/9936/lastscannd1.jpg
OKay here is my reasoning:

For the first one, which is invalid.

they say For n >= 3, assume that P(k) is true for all k >=1 such that k <= n. So k <= 3. We will porve that P(n) is true.
Assumes P(1), P(2), P(3)
Is it invalid because P(3) wasn't proven true in the beginning, it ony said:
P(1) and P(2) are true.For the 2nd, which is valid.
For n >= 2, assume that P(k) is true for all k >= 1 such that k < = n, so
k <= 2. We will prove that P(n+1) is true.
Proves: P(1), P(2), and P(2+1) = P(3).
Assumes P(1) and P(2) are true, which it is, from the first pargraph, so that must be valid.

For the 3rd, which is also valid:
For n > 3, assume that P(k-1) is true for all k >= 2 such that k < n. We will prove that P(n-1) is true.
Proves P(1),P(2), P(3), and P(4)
assumes P(1), P(2).

So k = 2, 3, 4
n > 4, so n = 4
assumes P(k-1) so we have:
assumes P(3), P(2), P(1)

But what confusees me is, if its assuming P(1),P(2), and P(3), and P(4),
the beginning paragraph didn't say P(3) and P(4) were true, so why is this valid?
For the 4th one, which is invalid:
FOr n > 3, assume that P(k) is true for all k >= 1 such that k < n. We will prove that P(n) is true.
Prove: P(n), and n > 3, so it will prove P(4), P(5), P(6)
assume P(k) is true for all k >=1 such that k < n.
So, k = 1, 2, 3
assume P(1), P(2), P(3),
we are assuming P(3) but there is no proving of P(3) becuase the proving starts at P(4) is that why this is invalid?For the 5th one, which is invalid

For n >=3, assume that P(K) is true for all k >= 0 such that k < n. We will prove that P(n) is true.

n = 3, 4, 5...
k = 0, 1, 2, 3, 4, 5...

assumes: P(0),P(1),P(2),P(3)
proves: P(3), P(4), P(5)

is this invalid because again ur assuming P(3), when P(3) wasn't proven to be true in the beginning paragraph?For number 6, which is valid:
For n >= 1, assume that P(k) is true for all k >=1 such that k <= 2n. We will prove that P(2n+1) and P(2n+2) are true.Proves n = 1: P(3) and P(4)
assumes n = 1: P(1), P(2)

Proes n = 2: P(5) and P(6)
assumes n = 2: P(1),P(2),:(3),P(4)

I see this is convering all the spots but for n = 1, why does it stop at P(2), and for n = 2, why does it stop at P(4)?Thanks!

 

[mighty2000]

Hello, it seems like you are on the right track with your reasoning! Let me provide some clarification and explanation for each of the scenarios:

1. For the first one, you are correct in saying that it is invalid because P(3) was not proven to be true in the beginning. The assumption is that P(1) and P(2) are true, but there is no mention of P(3) in the beginning. This means that the proof is incomplete and therefore, invalid.

2. For the second one, you are also correct in saying that it is valid. The proof follows the assumption that P(1) and P(2) are true, which was stated in the beginning. It also proves P(3), which is consistent with the assumption. So this proof is valid.

3. For the third one, you are correct in saying that it is valid. The assumption is that P(1), P(2), P(3), and P(4) are true, and the proof follows this assumption. The fact that P(3) and P(4) were not explicitly mentioned in the beginning is not a problem, as they are still within the range of the assumption (k-1 is equal to 3 and 4 in this case).

4. For the fourth one, you are correct in saying that it is invalid. The assumption is that P(1), P(2), and P(3) are true, but the proof only goes up to P(3). This means that P(4) and any other values of k are not considered, making the proof incomplete and therefore, invalid.

5. For the fifth one, you are also correct in saying that it is invalid. The assumption is that P(0), P(1), P(2), and P(3) are true, but the proof only goes up to P(3). This means that P(4) and any other values of k are not considered, making the proof incomplete and therefore, invalid.

6. For the sixth one, you are correct in saying that it is valid. The assumption is that P(1) and P(2) are true, and the proof follows this assumption by proving P(3) and P(4). This pattern continues for n = 2, 3, 4, etc. and the proof covers all the necessary cases. The reason why it stops at P(