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

Click For Summary

Discussion Overview

The discussion revolves around proving a proposition p(n) related to a sorted vector of integers, specifically addressing the truth of p(n) for all integers n within a defined range. The participants explore the implications of the properties of the vector and the concept of mathematical induction.

Discussion Character

  • Mathematical reasoning
  • Homework-related
  • Exploratory

Main Points Raised

  • Post 1 introduces the proposition p(n) and provides an initial proof for p(1), asserting that v.at(1) is greater than or equal to 12.
  • Post 2 suggests leveraging the sorted nature of the vector and the uniqueness of its elements to further the proof.
  • Post 3 attempts to apply the proposition to subsequent values of n, indicating a misunderstanding of the induction process.
  • Post 4 questions the implications of the sorted vector, noting that v.at(n) must be greater than v.at(n-1).
  • Post 5 confirms the previous point and seeks clarification on the role of the inductive hypothesis.
  • Post 7 proposes using the properties of integers and the relationship between consecutive elements to facilitate an inductive proof.
  • Post 8 expresses confusion regarding the application of induction in this context, suggesting a disconnect with the learning material.
  • Post 9 conveys frustration with the inability to synthesize the information into a coherent proof.

Areas of Agreement / Disagreement

Participants generally agree on the properties of the vector and the potential for using induction, but there is no consensus on how to effectively apply the inductive hypothesis or complete the proof.

Contextual Notes

Participants express uncertainty about the application of mathematical induction in this scenario, highlighting a lack of clarity in the learning materials they are using.

ZERO_COOL
Messages
17
Reaction score
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).
 
Physics news on Phys.org
Try using the facts that v is sorted and no two elements of v are the same. What does this tell you?
 
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)
 
If they are sorted and no two are the same, doesn't this mean that v.at(n)>v.at(n-1)?
 
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?
 
I'm still struggling to work this out, so any help appreciated.
 
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?
 
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.
 
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.
 

Similar threads

Undergrad Question about mathematical induction
  • · Replies 10 ·
Replies
10
Views
2K
Prove that ##5 | (2^n a) \rightarrow (5 | a)##for any ##n##
  • · Replies 10 ·
Replies
10
Views
4K
Undergrad Computing the expectation of the minimum difference between the 0th i.i.d.r.v. and ith i.i.d.r.v.s where 1 ≤ i ≤ n
  • · Replies 0 ·
Replies
0
Views
2K
Mathematical Induction with binomial sum
  • · Replies 9 ·
Replies
9
Views
4K
MHB Understanding induction proof of pigeonhole principle
  • · Replies 4 ·
Replies
4
Views
4K
If p is even and q is odd, then ##\binom{p}{q}## is even
  • · Replies 19 ·
Replies
19
Views
4K
Prove Fibonacci identity using mathematical induction
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Can you make the induction step by contradiction?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Proof of Induction Principle starting from N, not from 1
  • · Replies 6 ·
Replies
6
Views
2K
Proving p(n): v.at(n) => 11 + n
  • · Replies 6 ·
Replies
6
Views
3K