Some simple summations

April 12th, 2004 admin Posted in Tidbits |

Old problems are sometime good to sit and ponder because you know that the solution is not beyond you, but at the same time you can challenge yourself to get back into the frame of mind of thinking about these issues. One such problem is the summation
1 + n + n(n-1)/2 + n(n-1)(n-2)/2.3 + … + n + 1
Do you know of a way to reduce this? How about using plain algebra?

Sum of all fears or fear of some sums

I love my work at IBM, when it leads an unsuspecting me around a boring corner, and brings me before a teasingly recognizable view … a pattern which you know you have seen before, but never expected to see here. And a little staring and thinking brings back a feared-forgotten world of wonderfully rich supporting mathematics. I was reading up a paper on RAID (Redundant Array of Inexpensive Disks) Technology, when I was led into thinking about this problem.
I want to prove that
ⁿC₀ + ⁿC₁ + ⁿC₂ + … + ⁿC_n = 2ⁿ
Mind the direction, it goes from the summation to the single term. After toiling with it for a while I sent out a note to my IIT Guwahati egroup and recieved the expected enthusiasm for not just finding the solution, but raising new sub-questions. Here I will provide some intersting points that came out of the discussion and the three ways of proving the equality. The one I was after in particular, a purely algebraic way of getting from LHS (left hand side) to RHS (right hand side), still eludes me.
I had figured out that proving the LHS, starting out from the RHS is easy.
2ⁿ = (1+1)ⁿ = ⁿC₀ + ⁿC₁ + ⁿC₂ + … + ⁿC_n, by the binomial expansion. Interstingly enough this gives rise to another question. How do you show that the binomial expansion is correct? What is the binomial expansion saying? And what is all this ⁿC_k business?

Many of my friends suggested the mathematical induction approach to the problem. That is show that for the trivial case it holds. That is, say n=1.
¹C₀ + ¹C₁ = 2 = 2¹
Let us say it holds for n = k. That is,
^kC₀ + ^kC₁ + ^kC₂ + … + ^kC_k = 2^k
Then what happens when n = k+1? If we can show that the equality still holds, we would have proven the equality by mathematical induction.
LHS would now look like,
^k+1C₀ + ^k+1C₁ + ^k+1C₂ + … + ^k+1C_k+1
Taking a general term in this series to be ^k+1C_l, we can simplify that term using the definition of ⁿC_k.
^k+1C_l = (k+1)!/l! . (k+1-l)!
= (k+1) . k!/(k+1-l) . (k-l)! . l!
= [(k+1)/(k+1-l)] . ^kC_l
= [1 + l/(k+1-l)] . ^kC_l
= ^kC_l + [l/(k+1-l)].^kC_l
= ^kC_l + [l/(k- l+1)].^kC_l
= ^kC_l + [l/(k- l+1)].[k!/l! . (k-l)!]
= ^kC_l + k!/(l-1)! . (k-l +1)!
= ^kC_l + k!/(l-1)! . (k- (l-1))!
= ^kC_l + ^kC_l-1
Thus using this breakdown for every term from the second to the second to last,
^k+1C₀ + (^kC₁ + ^kC₀) + (^kC₂ + ^kC₁) + … + (^kC_k + ^kC_k-1) + ^k+1C_k+1
Separating the first and second terms in the bracketed pairs, and the first and last term into two groups
[^k+1C₀ + ^kC₁ + ^kC₂ + … + ^kC_k] + [^kC₀ + ^kC₁ + … + ^kC_k-1 + ^k+1C_k+1]
Since the first term in the first bracket and the last term in teh second bracket sum are same as ^kC₀ and ^kC_k respectively, we effectively have
[^kC₀ + ^kC₁ + ^kC₂ + … + ^kC_k] + [^kC₀ + ^kC₁ + … + ^kC_k-1 + ^kC_k]
which from our assumption step in the induction process, is
2ⁿ + 2ⁿ
= 2ⁿ⁺¹

Another way to prove the same idea is to show that LHS and RHS describe the same thing. This is like showing LHS = X and RHS = X, so LHS = RHS. Instead of getting very formal about the proof, I will stick to a light hearted example here. I am repeating the example I wrote in our egroup discussion, as is …
Lets say Anupam Singh comes back home after a hard day at work. Then he decides to go play pool with Nadeem sahab. After getting beaten badly multiple number of times, he decides to give up. He puts all the pool balls (numbered 1 to 15) into his backpack and says enough is enough. He is ready to go back home. Nadeem, being the smart alec he is, tells him, I want to play so give me the balls back. Anupam Singh says OK I will put my hand into the backpack, and take out whatever I choose to take out. You will get only those balls to play with. Obviously Nadeem has no clue how to play pool with less than 15 balls (forget the cue ball for now, that is supplied by CK). So suspecting foul play he says, “You can’t trick me. You will keep taking out fewer balls everytime.”. Anupam says, “OK, I will promise you this, I will take out a different set of balls every time. So eventually you will get all the 15 balls out and then you can play with them all.” Nadeem being the innocent smart alec that he is, says OK. (CK is meanwhile way ahead of the game, for he has already calulated in his notebook that Nadeem is done for the night). How many times can Anupam Singh take a unique combination of balls out of his backpack before he finally has to take them all out?
He can take out nothing at all the first time. He then has to take out at least one ball the next time. In order to not repeat a combination, he can choose each single ball once, making that 15 (or n) times. He can choose 2 out of the 15 in ¹⁵C₂ ways. When he decides to take out only 3, he can do that ¹⁵C₃ ways… by next morning, he has exhausted the following number of options.
¹⁵C₀ + ¹⁵C₁ + ¹⁵C₂ +… ¹⁵C₁₄… and so finally he decides to take out all the 15 in ¹⁵C₁₅ =1 way.
Looked at another way, every time Anupam Singh draws out a combination from the bag, he either takes out ball no. 1 or does not, either takes out ball no. 2 or does not , … ,either takes out ball no. 15 or does not. This means there are 2 possibilities for ball 1 AND 2 possibilities for ball 2 AND …2 for ball 15. i.e, there are 2^15 ways of doing this not-so-intelligent a deal. So therefore, ¹⁵C₀ + ¹⁵C₁ + ¹⁵C₂ +… ¹⁵C₁₅ = 2¹
LHS leads to RHS. No induction.
If you know how to solve it directly from LHS to RHS using simple algebra, I would appreciate your pointers to it.

Binomial Expansion

The way I think about binomial expansion is this way.
Lets say, taking a pretty general case, you want to expand
(a+b)ⁿ
= (a+b)(a+b)(a+b)…(a+b) with n terms. Call this equation 1.
This can be written as a SUM of products. These product terms should basically satisfy the following property. They should be all the various products of a’s and b’s such that the total number of a’s and b’s are n. Why? Because you are trying to go to each bracketed pair in the above equation 1 and picking either the a or the b from the (a+b). There is no other go. You have to choose either of the two from every term. And no two product terms should pick the exact same sequence of a’s and b’s. Meaning if you have chosen aabbbbbbb (as an example with n=7) you can not choose aabbbbbb again, though you can choose abbbbbba, which effective shows that there are repeating terms in the sum of products form of equation 1. (Actually that sum of products is the binomial expansion)
So the terms can be only of the following types
all a’s (aaaaaaa for the case n=7)
n-1 a’s and 1 b (aaaaaab, aaaaaba,… etc)
n-2 a’s and 2 b’s … and so on till
all b’s
This means all we need to do is figure out how many terms of each product there are (since we saw earlier that there can be multiples).
How many “all a’s” terms? How many ways can you choose no b’s (all a’s) from the n (a+b) terms in equation 1? ⁿC₀ ways.
How many “n-1 a’s and 1 b” terms? How many ways can you choose 1 b from n (a+b) terms in equation 1? ⁿC₁ ways.
And so on.
So the sum of products becomes
ⁿC₀. aⁿ + ⁿC₁. a^n-1. b + ⁿC₂. a^n-2.b² +…+ ⁿC_n. bⁿ
BTW, ⁿC₀, ⁿC₁ are by definition “number of ways to choose 0 or 1 out of n” To prove the ⁿC_k = n!/(k!.(n-k)!) is another interesting but simple problem.

What is ⁿC_k? Why is ⁿC_k = n!/(k!. (n-k)!) ?

Say you have n balls labeled 1 through n. And you have to choose k balls, with no importance given to the order of choosing. The numbers of unique ways you can choose, provided the order of choosing is unimportant, only the set chosen is important, is called “n choose k” and denoted by the shorthand notation ⁿC_k.
You can choose the first ball in n ways, because you have n to choose from from the first ball. Once you choose the first ball, you have only n-1 remaining (since you cannot choose the first ball again). You’ll have n-2 choices to choose the third ball and n-(k-1) ways to pick the k^th ball. You wanted k balls. So there are
n ways to choose the 1^st AND you have n-1 ways to choose the 2^nd AND … n-(k-1) ways to choose the k^th ball.
= n.(n-1).(n-2).(n-3)…(n-(k-1))
= n.(n-1).(n-2).(n-3)…(n-(k-1))[(n-k)(n-k-1)…3.2.1]/[(n-k)(n-k-1)…3.2.1]
= n!/(n-k)!
But we have overlooked an important fact here. There is no check in the above calculation to ensure that we do not end up with the exact same combination of balls, chosen in a different order, in different attempts. For example if there are 3 balls, choosing 1,2 and then 3 will be the same effective combination as choosing 2,3 and then 1. Hence we have to divide the above number by the number of ways the same set of k chosen balls could have shown up, in unique choice orders. This is basically a way of saying how many ways can k balls be uniquely ordered. The way to think of that is, the first ball can be placed in any one of k positions, starting from position 1 in the ordering to position k. Once the first ball has been placed, the second one only has a choice of k-1 positions. And similarly the second ball has k-2 options and the final ball has only one place it can go. Therefore this means there are k.(k-1).(k-2)…2.1 ways to arrange k balls in k positions. This is k!.
Hence the number we are after, ⁿC_k
= number of ways to choose k balls from n balls / number of unique orderings that the same choice of k balls can take while choosing the k balls from n balls
= n!/(n-k)! / k!
= n!/(k! . (n-k)!)
Interstingly, the intermediate result we got n!/(n-k)! is the number of permutations of k objects from a set of n unique objects!