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.

  • 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
    @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