Induction With Binomial CoefficientsDate: 10/16/2000 at 11:31:44 From: Bill Lee Subject: Number theory - Summation Notation I am in the process of studying number theory, and I was poring over a problem regarding summation and multiplicative notation. The problem that I was given and can not seem to grasp is this, and I will say I truly do not know where to begin. Prove that: n i+k-1 n+k SUM ( ) = ( ) i=1 k k+1 where n and k are integers with n >= 0 and k >= 0. For me, Dr. Math, here is the really sticky part. The problem goes on to say that it is customary to set a ( ) = 0 for integers a and b if 0 <= a < b. b Can you help me with this one? Thanks. Date: 10/16/2000 at 13:42:29 From: Doctor Rob Subject: Re: Number theory - Summation Notation I'm not sure what method of proof you are supposed to use here, but a proof by mathematical induction on n is not very hard. The base case is n = 0, in which case the sum on the left is the empty sum, or 0, and the right-hand side is also 0 by the remark about "customary." For n = 1, the left side is 1 and the right side is also 1. Suppose you know the stated equation is true for n and all values of k >= 0. Then n+1 i+k-1 n i+k-1 n+1+k-1 SUM ( ) = SUM ( ) + ( ), by what the notation means, i=1 k i=1 k k n+k n+k = ( ) + ( ), by the induction hypothesis, k+1 k (n+1)+k = ( ), by using the identity for binomial k+1 coefficients from Pascal's triangle. Thus the equation is also true for n+1 and all values of k >= 0. Then apply the Principle of Mathematical Induction to conclude that it is true for all values of n >= 0 and all values of k >= 0. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ Date: 10/17/2000 at 23:22:00 From: Bill Lee Subject: Re: Number theory - Summation Notation Thank you, Dr. Rob, for responding so quickly to my question. I do understand your point of view for this proof, meaning proof by induction is one way, but I am still confused on the notation of it all. In my experience with mathematical induction, I have never seen a ( ) = 0 b used in mathematical induction. I thought that this notation might be related to eigenvectors in linear algebra. Is this true or am I in left field on this one? I guess what I am saying is that I see how the induction process could be one way to solve this problem, but I am not sure I follow your proof of it. Is there a way that you could help me understand this a little better? When this problem was presented in class, there was no mention of mathematical induction as a way to solve it. I would like to know why you chose mathematical induction and how induction fits with the notation that is given in the stated problem. Once again, I appreciate all your help with this. Any light that you could shed on this issue would be most appreciated. Thank you. Date: 10/20/2000 at 14:01:23 From: Doctor Rob Subject: Re: Number theory - Summation Notation Thanks for writing back. You wrote: >... I am still confused on the notation of it all. Is it the summation notation or the binomial coefficient notation that you find confusing? >In my experience with mathematical induction, I have never seen > > a > ( ) = 0 > b > >used in mathematical induction. Good! That means I have shown you something new, and you have a chance to learn from the experience. >I thought maybe that this notation might be related to eigenvectors >in linear algebra. Is this true or am I in left field on this one? The relation between these ideas is either very remote or nonexistent. >When this problem was presented in class, there was no mention of >mathematical induction as a way to solve it. I warned you that this might not be the way that the poser of the problem wanted this proved. I would be interested in what method was used, if you care to tell it. (I have a sneaking suspicion that whatever proof was presented has a hidden induction concealed within.) >I would like to know why you chose mathematical induction and how >induction fits with the notation that is given in the stated problem? The notation n SUM a(i) i=1 is defined to mean this: consider the sequence a(i) for 1 <= i <= n, and add up all those terms of the sequence, or, in symbols, a(1) + a(2) + ... + a(n-1) + a(n) If there is just one term, no adding takes place, and you just have a(1). (This is the result of adding up a column of 1 row of numbers containing a(1).) If there are no terms, no adding takes place, and you just have 0. (This is the result of adding up a column with 0 rows of numbers.) The summation notation is used to dispose of those annoying dots in the ellipsis "..." above, and to make rigorous the phrase "and so on" implied by them. If you change n to n+1 in the either expression above, what you get is a sum with one additional summand, namely a(n+1). That is what suggests using induction, that the sum of the first n terms can be separated from the (n+1)st term in this way. Then the induction hypothesis can be applied to the first part, and somehow the last term can be combined with the result of using the hypothesis to prove the induction step. In the proof I gave, I did just that to establish the induction step. I assumed the statement was true for some particular value n, and then wrote down one side of the equation for the statement corresponding to the next value of n, that is, n+1. Then I separated the last term from the first n terms and applied the induction hypothesis to the first part, getting an expression for the sum of the first n terms as a single binomial coefficient. Then I combined that binomial coefficient with the one that was the last term of the sum. This was easy to do by the rule for Pascal's triangle, which states that every number in the triangle is the sum of the two above it. The two coefficients we have are adjacent entries on the same line of the triangle, so their sum is the one between them on the next line of that triangle. That gave us the sum as a single binomial coefficient, and that was just what was needed for the right-hand side of the equation for the statement corresponding to n+1. I hope this is clearer. If not, write again. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/