Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Clive Newstead Sep 11 '12 at 13:45
    
I only fixed the formatting of the question. I second @CliveNewstead's comment. What's the upper limit of the sum? –  Ayman Hourieh Sep 11 '12 at 13:47
    
And what's your definition of $\sum$? Usually this is how it's recursively defined. –  ronno Sep 11 '12 at 13:50
    
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). –  Michael Guantonio Sep 11 '12 at 14:06
    
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. –  Bill Dubuque Sep 11 '12 at 14:33
show 8 more comments

2 Answers

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.

share|improve this answer
    
I had mistakenly given you the wrong equation. –  Michael Guantonio Sep 11 '12 at 19:55
    
@MichaelGuantonio: That's okay, just subtract $1$ from everything :) –  Clive Newstead Sep 11 '12 at 20:03
add comment

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.

share|improve this answer
    
I have mistakenly given you the wrong equation. –  Michael Guantonio Sep 11 '12 at 19:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.