Mathematical Induction Proof

  • Thread starter ZERO_COOL
  • Start date
  • #1
17
0
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).
 

Answers and Replies

  • #2
phyzguy
Science Advisor
4,601
1,556
Try using the facts that v is sorted and no two elements of v are the same. What does this tell you?
 
  • #3
17
0
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)
 
  • #4
phyzguy
Science Advisor
4,601
1,556
If they are sorted and no two are the same, doesn't this mean that v.at(n)>v.at(n-1)?
 
  • #5
17
0
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?
 
  • #6
17
0
I'm still struggling to work this out, so any help appreciated.
 
  • #7
phyzguy
Science Advisor
4,601
1,556
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?
 
  • #8
17
0
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.
 
  • #9
17
0
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.
 

Related Threads on Mathematical Induction Proof

  • Last Post
Replies
11
Views
1K
Replies
2
Views
7K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
8
Views
5K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
1K
Top