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

• mr_coffee
In summary: P(2n+1) and P(2n+2) are equivalent to P(3) and P(4) in this case. Similarly, for n = 2, it stops at P(4) because P(2n+1) and P(2n+2) are equivalent to P(5) and P(6). So the proof is still valid even though it doesn't explicitly mention P(3) for n = 1 and P(5) for n = 2.In summary, the first and fifth scenarios are invalid because the proofs are incomplete and do not cover all necessary cases. The second, third, and sixth scenarios are valid because
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!

Last edited by a moderator:

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(

## What is a strong induction?

A strong induction is a proof technique used in mathematics to prove that a statement is true for all natural numbers. It involves breaking the statement down into smaller parts and proving that it is true for the smallest value, and then using the assumption that it is true for all smaller values to prove that it is also true for the next value. This process is repeated until the statement is proven to be true for all natural numbers.

## How can a strong induction be translated into test cases?

A strong induction can be translated into test cases by identifying the smaller parts of the statement and creating test cases to prove that these parts are true for the smallest value. Then, using the assumption that these smaller parts are true, additional test cases can be created to prove that the statement is true for the next value. This process is repeated until all values have been tested.

## What should be considered when determining if a test case is valid or invalid?

When determining if a test case is valid or invalid, it is important to consider whether the test case accurately reflects the statement being tested. The test case should also cover all possible scenarios and be able to produce the expected result. Additionally, the test case should be feasible and able to be executed within a reasonable amount of time.

## What are some common answers given when translating a strong induction to test cases?

Some common answers given when translating a strong induction to test cases include breaking the statement down into smaller parts, using the assumption that these smaller parts are true, and testing for all possible scenarios. Other answers include creating test cases that are feasible and accurately reflect the statement being tested.

## What are the benefits of using a strong induction to create test cases?

Using a strong induction to create test cases can help ensure that all possible scenarios are tested and that the statement is proven to be true for all natural numbers. It also allows for a systematic approach to testing, making it easier to identify any errors or issues that may arise. Additionally, using a strong induction can help in creating more efficient and effective test cases.

Replies
9
Views
2K
Replies
3
Views
386
Replies
6
Views
2K
Replies
12
Views
2K
Replies
8
Views
1K
Replies
4
Views
1K
Replies
1
Views
111
Replies
15
Views
3K
Replies
2
Views
2K
Replies
6
Views
806