lew@ihuxr.UUCP (08/11/83)
I received several responses to my combinatorial identity article. The idea was to prove: sum i=1,n of (-1)^(i+1) * C(n,i) * 1/i == sum i=1,n of 1/i Harry Bims, Dave Sibley and arizona!gary sent me inductive proofs. I had included an attempt at this in my posting. None of them noticed that my attempt was just one step short of completion. (Of course I hadn't noticed it either!) I had reduced the inductive step to: sum i=1,n of (-1)^(i+1) * C(n,i)/(n+i-1) == 0, n even ; 2/(n+1), n odd Multiplying through by (n+1) reduces this to: sum i=0,n of (-1)^i * C(n,i) = 0 This is in Abramowitz and Stegun, and is easily shown to be true by taking the binomial expansion of ( 1 + (-1) )^n. (Hao Nhien Vu noticed this, but didn't know how to show the very last step.) David Goldberg sent me a proof based on integrating both sides of: sum i=1,n of C(n,i) * x^(i-1) == ( (1+x)^n - 1 )/x Roy Haas also showed this to me. This is probably the officially approved method, since it uses generating functions, but the algebra in the inductive method is a lot more fun. Darrel Plank sent me a proof which used an intermediate definition of a sum S(n,k), which was a combination of the first k terms of the harmonic sum and n-k combinatorial terms. S(n,n) was the harmonic sum and S(n,0) was the desired combinatorial sum. He then showed that S(n,k) == S(n,k+1) for 0<=k<n. This was the most interesting proof. Dave Sibley suggested I might find something about this in Knuth's "The Art of Programming", but I looked there and I didn't find anything very close. (It isn't in Abramowitz and Stegun either.) This identity must be in print someplace, but it doesn't seem to be worth an all out search, to say the least. Thanks to all who responded. Lew Mammel, Jr. ihuxr!lew