1
$\begingroup$

I am trying to solve this problem by induction. The sad part is that I don't have a very strong grasp on solving by inductive proving methods. I understand that there is a base case and that I need an inductive step that will set $k = n$ and then one more step that basically sets $k = n + 1$.

Here is the problem I am trying to solve:

If $f(n) = \sum_{i = 0}^n X_{i}$, then show by induction that $f(n) = f(n - 1) + X_{n-1}$.

Can I have someone please try to point me in the right direction?

*EDIT: I update the formula to the correct one. I wasn't sure how to typeset it correctly and left errors in my math. Thank you for those that helped. I'm still having the problem but now I have the proper formula posted.

  • 1
    I presume you mean $f(n) = \displaystyle \sum_{i=1}^n X_i$ and $f(n) = f(n-1) + X_n$ rather than what you wrote.2012-09-11
  • 0
    I only fixed the formatting of the question. I second @CliveNewstead's comment. What's the upper limit of the sum?2012-09-11
  • 0
    And what's your definition of $\sum$? Usually this is how it's recursively defined.2012-09-11
  • 0
    I'm sorry I am unfamiliar with the code tags for a math type setting. The limit is actually i = 1 to n-1. And the second part of the equation should be f(n-1) + x ^ (n-1).2012-09-11
  • 0
    Could you please write the problem *precisely* as it was stated, because the above can be interpreted in various ways. Do you already have available some rigorous definition of the sum that differs from the stated recursion? One most employ great care here to avoid circular proofs.2012-09-11
  • 0
    From the source: Let $$f(n) = \displaystyle \sum_{i=1}^{n-1} X^{i}$$. Show that $$f(n) = f(n -1) + x^{n-1}$$2012-09-11
  • 0
    What is the source? Does it say to use induction? Does it discuss inductive/recursive definitions before this? To reply to someone you need to write @username else they will not be notified.2012-09-11
  • 0
    @BillDubuque The source is a homework problem. It does not discuss any type of recursive/inductive definitions. That is the question in its entirety. It does not build from any previous questions it is just asking for a proof. I thought that proof by induction was a good method to try.2012-09-11
  • 0
    @Michael A homework problem from where? A class in discrete math, or algorithms, or foundations of math? What is your textbook?2012-09-11
  • 0
    @BillDubuque This is a class on algorithms and data structures. We are using Introduction to Algorithms 3rd edition. My professor is what many would call very very unclear on explaining how to derive and solve these algorithms and I fear that teaching myself is making me only more confused.2012-09-11
  • 0
    If you wish to understand this *rigorously* then you need to understand so-called inductive or recursive definitions. For a rigorous and insightful introduction see the award-winning Monthly exposition of Leon Henkin mentioned in my related posts [here](http://math.stackexchange.com/a/143539/242) and [here.](http://math.stackexchange.com/a/120586/242) Many algorithm textbooks gloss over these formalities at the cost of rigor. It's hard to know what the appropriate compromise may be for your course without knowing further details.2012-09-11
  • 0
    @BillDubuque Thank you, I will take a look. I wish I knew what was really expected in this course as well. I would be all for proving and showing if an algorithm is correct or not if my professor actually knew what was going on. Most of the time its just him trying to solve his own lecture problem (which doesn't help much with strategy.)2012-09-11
  • 0
    Why isn't "That's the _definition_ of $\sum$." the complete proof?2012-09-14

2 Answers 2