Proving p(n): v.at(n) => 11 + n

[ZERO_COOL]

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.

 

[Mark44]

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

It is given that v.at(1) = 12, and 12 = 11 + 1, so p(1) is true.
You are using the proposition to show that the proposition is true, which is not valid. This is your step that I am questioning: v.at(1) => 11 + 1.

BTW, what's with the => symbol? Doesn't = work just a well?

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.

No, you can't do this.

Start by assuming p(k - 1) is true. I.e., v.at(k - 1) = 11 + (k - 1) = 10 + k.
Now use this, plus the other given information, to conclude that p(k) = 11 + k. (How to do this isn't obvious to me.)

BTW, don't write p(k) = ... p(k) represents a particular statement. Its value is either true or false.

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.

 

[Mark44]

I think that the key to this problem is that your vector has only a finite number of elements. IOW, there is a last element at index v.size(). This is different from most induction proofs, where the index is an element of the positive integers, a set without a largest element.

 

[ZERO_COOL]

Can anyone else help with this?

 

[LCKurtz]

I'm guessing the problem is in the notation. You have written

p(k)=>k + 11

which looks like some kind of implication symbol. Are you actually trying to prove:

p(k) ≥ 11 + k ?

That is very easy to show. Is that really what your question is?

 

[Mark44]

I'm guessing the problem is in the notation. You have written

p(k)=>k + 11

which looks like some kind of implication symbol. Are you actually trying to prove:

p(k) ≥ 11 + k ?

That is very easy to show. Is that really what your question is?

From the OP,

p(n): v.at(n) => 11 + n.

p(n) is proposition/statement n. The statement itself is v.at(n) >= 11 + n. Here, v is an instance of the vector class in C++, and at(n) is a function that returns a reference to the value at index n.

 

[LCKurtz]

From the OP,

p(n) is proposition/statement n. The statement itself is v.at(n) >= 11 + n. Here, v is an instance of the vector class in C++, and at(n) is a function that returns a reference to the value at index n.

Maybe I just don't see what the problem or what it has to do with C++ or its vector class. Isn't he just asking this question:

Given sequence of {v(n)} of integers which is sorted with v(1) = 12, show that v(n) ≥ 11 + n for all positive integers n? That is a perfectly sensible and easily proven statement. If that isn't what the question is, I need more clarification.