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

  • Thread starter ZERO_COOL
  • Start date
In summary: 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.
  • #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.
 
Physics news on Phys.org
  • #2
ZERO_COOL said:

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?
ZERO_COOL said:
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.
ZERO_COOL said:
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.
 
  • #3
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.
 
  • #4
Can anyone else help with this?
 
  • #5
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?
 
  • #6
LCKurtz said:
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.
 
  • #7
Mark44 said:
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.
 

1. How do you prove p(n)?

To prove p(n), you must show that the statement v.at(n) => 11 + n is true for all values of n. This can be done through various methods, such as mathematical induction or direct proof.

2. What does v.at(n) mean?

v.at(n) is a mathematical notation that represents a variable or function at a specific value of n. In this case, it could be any variable or function, as long as it is consistent throughout the proof.

3. Can you explain the significance of 11 + n in the statement?

The statement 11 + n represents a specific condition or result that is being proven to hold true. It could represent any equation or expression that has a specific value when n is substituted in.

4. How do you know if p(n) is true?

If you are able to successfully prove that the statement v.at(n) => 11 + n is true for all values of n, then p(n) is considered true. This means that the statement holds true for any possible value of n.

5. What is the purpose of proving p(n)?

The purpose of proving p(n) is to provide evidence or justification for a mathematical statement. It allows us to verify that a statement holds true for all possible values of n, providing a stronger foundation for future mathematical work or applications.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
848
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
32
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
27
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
588
Back
Top