- #1
ZERO_COOL
- 17
- 0
Homework Statement
Suppose that v is of type Vector of Integers and we know the following:-
1. v is sorted.
2. No two items in v are the same.
3. v.at(1) is 12.
For an integer n, where 1 <= n <= v.size(), let p(n) be the following proposition: p(n): v.at(n) => 11 + n.
A. Explain why p(1) is true?
B. suppose that p(k - 1) is true (where 1 < k <= v.size()). Explain why p(k) must then be true.
C. Complete a proof that p(n) is true for all integers n with 1 <= n < v.size().
Homework Equations
The Attempt at a Solution
A.
Let n = 1.
p(1) = v.at(1) => 11 + 1 = 12
As per part 3, v.at(1) is 12 and so p(1) is true. This is the base step.
B.
As per parts 2 & 3, v.at(k - 1) < v.at(k). Then,
p(k) = v.at(k) => v.at(k - 1) + 1.
Thus p(k) is true. This is the inductive step.
C.
From the base step, p(1) = v.at(1) => 11 + 1 = 12.
Now, p(1) => 12 --> p(2) = v.at(2) => 11 + 2 = 13.
Hence, p(2) => 13 --> p(3) = v.at(3) => 11 + 3 = 14.
Hence, p(3) => 14 --> p(4) = v.at(4) => 11 + 4 = 15.
Hence, p(4) => 15 --> p(5) = v.at(5) => 11 + 5 = 16.
: :
: :
Now, p(k - 1) => 11 + k -1 --> p(k) = v.at(k) => 11 + k.
Thus, for any k => 1, p(k - 1) --> p(k) = v.at(k) => 11 + k.
Since the inductive step has been proven the proof is now complete.
*****
I'm not very confident with this and would really appreciate it if someone could double check it for me. I'm thinking most of C belongs in b because its basically proving the inductive step which is what b is asking.