Chinese Abacus and Mathematical Induction

When I was a kid, I used to practice Chinese Abacus every day. Me and my brother turn this boring practice into a competition, and the winner is the person who can do 1 + 2 + ... + 100 faster! Of course, it's has to be correct. At that time, we were told that the correct value is 5050, and we did not question about it.

Now, I kinda wonder, if I am going to proof to some one that 1 + 2 + ... + 100 = 5050, how can I do that?  Here one way to do it.

First line up two line of sum this way, one from 1 to 100, another from 100 to 1.

  1 +   2 +   3 + ... + 100
100 +  99 +  98 + ... +   1
---------------------------------------
101 + 101 + 101 + ... + 101 = 101 * 100

Then, sum each column. As you can see, sum value in each column is equal 101. Since we know that there is going to be 100 column. So the sum of the last line, which is sum of those two line, is 101 * 100. Because we start with 2 lines,  the sum of  \(1 + 2 + 3 + ... + 100\) = \(101 \cdot 100 / 2 = 5050 \).

This way, we can also show that, for any given interger \(n \ge 1\)
$$ \displaystyle\sum_{i=1}^{n} i = 1 + 2 +  ... + n = \frac{n\dot(n+1)}{2}$$
Nice!, It's probably require a genius to come up with the proof like this, don't you think?

Another way, we can use mathematical induction to proof this statement too. It's more systematic, and can be generalize to prove more complex statements. The proof by mathematical induction has two parts, basis step and induction step. Basically, we have to show the basis is true, then show if any given number is true, then the next one also true.



To proof by induction, we start with basis case: \(n = 1\)
\[ \displaystyle\sum_{i=1}^{1} i =  1  =  \frac{1\cdot (1+1)}{2} \]
Then, we assume the statement is true for any given number \(k\),
\( \displaystyle\sum_{i=1}^{k} i = \frac{ k (k + 1) }{2} \)
we have to show that the statement is also true for \(k + 1\), and here it is:

\begin{align*}
  \displaystyle\sum_{i=1}^{k + 1} i
  &=  \displaystyle\sum_{i=1}^{k } i + (k + 1)
  \\ &= \frac{k (k+1)}{2} + (k + 1)
  \\ &= \frac{k (k+1) + 2 (k + 1)}{2}
  \\ &= \frac{(k + 1) ((k + 1) + 1)}{2}
\end{align*}

Compare to the first method, mathematical induction seem to be more complicated. However, this method can be extended to prove more complex statements on more well-founded structures, such as graph, and trees. 

Next time we shall see how can we use mathematical inductions in other more complex problem.