Your inductive assumption is that .
Now you need to prove that . What do you get after using the sequence definition - for ?
For the second part, use the triangle inequality to get a geometric sum:
Hey guys, was hoping someone could walk me thru an induction proof
Im given: for
Prove that for all natural numbers n.
First is base case. We see that and base case done.
Now inductive step. Assume is true.....now what do I do?
I know how to set up a proof by induction of a sum, but these recurrence formulas just aren't clear yet.
After this, how would I go about proving an inequality using a recurrence formula...like this problem below:
Prove if then
Thanks!
Your inductive assumption is that .
Now you need to prove that . What do you get after using the sequence definition - for ?
For the second part, use the triangle inequality to get a geometric sum:
We have
(Assume the hypothesis holds for n)
We want to show
(Does the hypothesis hold for n+1?)
Which, notice, is equivalent to saying
We can decompose our x's quite easily:
Also, note that our induction hypothesis (the first equation I listed) implies
Therefore:
Now, substituting the values for the 's above, can you get this equation to look like one-half of the equation above it?