Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10 5/26/83; site ihuxr.UUCP Path: utzoo!linus!decvax!harpo!gummo!whuxlb!pyuxll!eisx!npoiv!npois!hogpc!houxm!hocda!spanky!burl!sb1!ll1!otuxa!we13!ihnp4!ihuxr!lew From: lew@ihuxr.UUCP Newsgroups: net.math Subject: Responses to "An interesting identity" Message-ID: <547@ihuxr.UUCP> Date: Thu, 11-Aug-83 13:03:36 EDT Article-I.D.: ihuxr.547 Posted: Thu Aug 11 13:03:36 1983 Date-Received: Sat, 13-Aug-83 03:23:36 EDT Organization: BTL Naperville, Il. Lines: 44 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