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

1

The way induction works is based on two steps:

  1. Check a base case.
  2. Show that if it holds for one number, then it holds for the next.

More formally, let $P$ be a property, and let $P(n)$ be the assertion that the property holds true for the natural number $n$; so for instance, $P(n)$ could be the assertion that $\sum_1^n i = \frac{n(n+1)}{2}$. Then to prove by induction that $P(n)$ holds for all $n \ge 1$, it suffices to

  1. Check that $P(1)$ holds;
  2. Check that, for any given value of $n$, if $P(n)$ holds then $P(n+1)$ holds.

Then we have a sort of domino effect. $P(1)$ holds as you showed for (1); and $P(2)$ holds because $2=1+1$ and $P(1)$ holds; and $P(3)$ holds because $3=2+1$ and $P(2)$ holds; and $P(4)$ holds because $4=3+1$ and $P(3)$ holds; and so on.

But here, induction is not necessary, since you can prove it directly for any given value of $n$. For any function $g$, $\displaystyle \sum_{i=1}^n g(i) = \sum_{i=1}^{n-1} g(i) + g(n)$ just by the definition of the $\sum$ symbol (unless you have a weird definition), and the result follows immediately from this fact.

  • 0
    I had mistakenly given you the wrong equation.2012-09-11
  • 0
    @MichaelGuantonio: That's okay, just subtract $1$ from everything :)2012-09-11
0

To prove by induction, you need to prove two things. First, you need to prove that your statement is valid for $n=1$. Second, you have to show that the validity of the statement for $n=k$ implies the validity of the statement for $n=k+1$. Putting these two bits of information together, you effectively show that your statement is valid for any value of $n$, since starting from $n=1$, the second bit that you proved above shows that the statement is also valid for $n=2$, and then from the validity of the statement for $n=2$ you know it will also be valid for $n=3$ and so on.

As for your problem, we proceed as follows:

(Part 1) Given the nature of your problem, it is safe to assume $f(0)=0$ (trivial sum with no elements equals zero). In this case it is trivial to see that $f(1)=f(0)+X_{1}$.

(Part 2) Assume the proposition is true for $n=k$, so $$f(k)=\sum_{i=1}^kX_i=f(k-1)+X_k$$ Adding $X_{k+1}$ to both sides of the equation above we get $$f(k)+X_{k+1}=\sum_{i=1}^kX_i=f(k+1)$$ So, the truth of the statement for $n=k$ implies the truth of the statement for $n=k+1$, and so the result is proved for all $n$. As Mr. Newstead said above, the induction step is not really necessary because of the nature of the problem, but it's important to have this principle in mind for more complicated proofs.

  • 0
    I have mistakenly given you the wrong equation.2012-09-11