Thread: Mathematical Induction Proof

I cannot get my head around this at all.

Suppose that v is of type Set 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().

Originally Posted by RedKMan

I cannot get my head around this at all.

Suppose that v is of type Set 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().

Your notation/terminology is a bit odd to me. Normally I'd call v a vector or a tuple instead of a set of integers. There seems to be a mixture of mathematics and computer science terms.

It seems clear from context that we are dealing with a k-tuple with indices going from 1 to k, as opposed to 0 to k-1.

But if I'm understanding the main question properly, the answer is intuitively very easy to understand. For any index i, the least possible value for v.at(i) is 11+i. This is because the tuple with minimal values is simply (12,13,14,15,...,11+k).

It can be seen that for the above tuple, it is not possible to replace v.at(i) with any value less than v.at(i), because then it would no longer be sorted and free from duplicate elements.

The rest is formalising with mathematical induction.

A. p(1) is true because p(1) = 12 >= 11+1 = 12. This is trivial.

B. So we assume that p(n-1) is true. Then the least possible value for p(n) is p(n-1)+1. So p(n) >= p(n-1)+1 >= 11+(n-1)+1 >= 11+n.

C. We have our induction step and base case. The proof is already complete.

Edit: By the way, "v is sorted" translates to v.at(1) <= v.at(2) <= v.at(3) <= ... <= v.at(k). Disallowing duplicates, this becomes v.at(1) < v.at(2) < v.at(3) < ... < v.at(k).

An equivalent way to state this is that given any two indices i and j, i < j, "v is sorted" implies that v.at(i) <= v.at(j). Disallowing duplicates, this becomes v.at(i) < v.at(j).