How can we prove that p(n) is true for all integers n with 1 <= n < v.size()?

[ZERO_COOL]

I cannot get my head around this at all.

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().

For A. I have,

In plain English the proposition means,
The n at position n in v is greater than or equal to 11 + n.

Let n = 1.

P(1): v.at(1) ≥ 11 + 1 = 12. (B)

From statement 3 which indicates v.at(1) is 12 and statement 2 which indicates no two items in v are the same, the above statement proves p(1) is true.

I'm struggling with the Inductive hypothesis (question b).

 

[phyzguy]

Try using the facts that v is sorted and no two elements of v are the same. What does this tell you?

 

[ZERO_COOL]

This tells me that:-

Let n = 2.

P(2): v.at(1) ≥ 11 + 2 = 13. (B)
P(3): v.at(1) ≥ 11 + 3 = 14. (B)
P(4): v.at(1) ≥ 11 + 4 = 15. (B)
P(5): v.at(1) ≥ 11 + 5 = 16. (B)

 

[phyzguy]

If they are sorted and no two are the same, doesn't this mean that v.at(n)>v.at(n-1)?

 

[ZERO_COOL]

Yes it does.

Given that v is sorted and no item in the vector is identical then:-

v.at(n) > v.at(n - 1).

Where does p(k - 1) come into play?

 

[ZERO_COOL]

I'm still struggling to work this out, so any help appreciated.

 

[phyzguy]

Since they are integers and v.at(n)>v.at(n-1), then v.at(n)>=v.at(n-1)+1. Can't you then work by induction?

 

[ZERO_COOL]

What your saying makes sense to me, I understand it. I'm not sure how p(k - 1) comes into play. I fairly sure I'm learning from bad text because the book is based entirely on using mathematical induction as proof for recurrence systems. Yet this question doesn't involve a recurrence system. I've tried looking for induction learning material but nothing I've come across really helps.

 

[ZERO_COOL]

Still struggling with this, feel as though I'm banging my head against a brick wall. I'm not sure how to put it all together into a meaningful proof.