| Sudha
Srinivasan |
We write down all the numbers 2,3,...,100, together with all their products taken two at a time, their products taken three at a time,and so on, up to and including the product of all 99 of them. What is the sum of the reciprocals of all the numbers written down? |
|||||||||||||||
| Mark
Durkee |
By two at a time, do you mean 2x3 + 3x4 + 5x6 +...+ 99x100 or (2x3 + 2x4 + 2x5 +...+ 2x100) + (3x4 + 3x5 +...+ 3x100) + ... + (99x100)? |
|||||||||||||||
| Sudha
Srinivasan |
2x3, 2x4, 2x5,...,2x99, 3x4,...3x99,...,98x99 we must take the reciprocal of all products and work out the sum |
|||||||||||||||
| Demetres
Christofides |
Replace 100 by any integer n> =2 and let f(n) be the corresponding sum. i.e. f(2) = 1/2 f(3) = 1/2 + 1/3 + 1/2*3 = 1 f(4) = 1/2 + 1/3 + 1/4 + 1/2*3 + ... + 1/2*3*4 = 3/2 Show that the following reccurence relation holds: f(n+1) = f(n) + (1 + f(n))/(n+1) i.e. (n+1)f(n+1) = (n+2)f(n) + 1 (*) There are now (at least) three ways of attack 1. Guess the answer and use (*) for the induction step (Try it, it's not that difficult in this case!) 2. Knowing f(n) you can calculate using (*) f(n+1). Use a computer to calculate f(100) [or do it by hand if you are not bored] 3. Try to solve the recurrence relation (*) (with initial condition f(2) = 1). This is usually done using generating functions. I can explain more if you want. Demetres |
|||||||||||||||
| Philip
Ellison |
Could you please explain method 3? I'd be interested to learn about generating functions, as I've seen mentions of them in a few places but never actually found out what they are, or how you use them! |
|||||||||||||||
| Arun
Iyer |
(Demetres,Sorry to break in to the discussion!) Generating Function for a sequence is a function whose coefficients are nothing but the numbers in sequence. To express it mathematically,if f(n) represents a particular sequence (i.e it gives the nth number in sequence) then the corresponding generating function is,
Now, can you see a way to link up Demetres' equation and the corresponding generating function of the sequence? love arun |
|||||||||||||||
| Demetres
Christofides |
No problem Arun. Let
the sum being from n=2 to infinity. This is a power series in z and we'll try to use (*) and the fact f(2)=1/2 to find F. You can differentiate and integrate F as you would expect (i.e. term by term) [If you want a justification of this try looking for 'ring of formal power series'] From (*) we have, for each n ³ 2 (n+1)f(n+1)zn=(n+2)f(n)zn+zn Summing from n=2 to infinity we get
(**) [All sums from n=2 to infinity] You should now use (**) to find a differential equation for F. For example the LHS of (**) is F¢(z)-2f(2)z=F¢(z)-z. [check] What's the RHS? [Note that
is a geometric progression.] Try to solve the differential equation. Then to find f(100) or in general f(n) there is another little trick that I will have to talk about. [unless you spot it] Demetres |
|||||||||||||||
| Sudha
Srinivasan |
Thanks Demetres, Your clue was very helpful! |
|||||||||||||||
| Philip
Ellison |
Thanks, Demetres and Arun. I've attempted a solution but can't complete it. Could you please tell me either what I'm missing or what I've done wrong. I got the RHS=zF'(z)+2F(z)+z2 /(1-z) The solution of the differential equation that I obtained was: F(z)=z2 /(1-z)2 Also, I think that F(n) (0)=n!f(n). I tried to use this in conjunction with the differential equation obtained before, but couldn't see any nice way of obtaining F(n) (0) in terms of n. Am I missing something obvious, have I made a slight slip, or am I completely wrong? (having never done anything like this before, I feel that I'm groping about in the dark!) |
|||||||||||||||
| Demetres
Christofides |
Can't remember what my RHS was but the answer is F(z) = (1/2)z2 /(1-z)2 Now a standard trick: 1/(1-z) = 1 + z + z2 + z3 + ... Now differentiate both sides and multiply by (1/2)z2 to find F(z) as a power series. Demetres |
|||||||||||||||
| Philip
Ellison |
Oops... that was a typo: I got the correct equation for F(z) but typed it up incorrectly! Nice trick, thanks. |
|||||||||||||||
| Panna Lal
Patodia |
To get the result, we need to write the small three line program in gp-pari. It gives value of f(z) from 1 to 100. ? f(z)=1/2*z^2/(1-z)^2 ? ps101 ? taylor(f(z),z) \%1 = 1/2*z^2 + z^3 + 3/2*z^4 + 2*z^5 + 5/2*z^6 + 3*z^7 + 7/2*z^8 + 4*z^9 + 9/2*z^10 + 5*z^11 + 11/2*z^12 + 6*z^13 + 13/2*z^14 + 7*z^15 + 15/2*z^16 + 8*z^17 + 17/2*z^18 + 9*z^19 + 19/2*z^20 + 10*z^21 + 21/2*z^22 + 11*z^23 + 23/2*z^24 + 12*z^25 + 25/2*z^26 + 13*z^27 + 27/2*z^28 + 14*z^29 + 29/2*z^30 + 15*z^31 + 31/2*z^32 + 16*z^33 + 33/2*z^34 + 17*z^35 + 35/2*z^36 + 18*z^37 + 37/2*z^38 + 19*z^39 + 39/2*z^40 + 20*z^41 + 41/2*z^42 + 21*z^43 + 43/2*z^44 + 22*z^45 + 45/2*z^46 + 23*z^47 + 47/2*z^48 + 24*z^49 + 49/2*z^50 + 25*z^51 + 51/2*z^52 + 26*z^53 + 53/2*z^54 + 27*z^55 + 55/2*z^56 + 28*z^57 + 57/2*z^58 + 29*z^59 + 59/2*z^60 + 30*z^61 + 61/2*z^62 + 31*z^63 + 63/2*z^64 + 32*z^65 + 65/2*z^66 + 33*z^67 + 67/2*z^68 + 34*z^69 + 69/2*z^70 + 35*z^71 + 71/2*z^72 + 36*z^73 + 73/2*z^74 + 37*z^75 + 75/2*z^76 + 38*z^77 + 77/2*z^78 + 39*z^79 + 79/2*z^80 + 40*z^81 + 81/2*z^82 + 41*z^83 + 83/2*z^84 + 42*z^85 + 85/2*z^86 + 43*z^87 + 87/2*z^88 + 44*z^89 + 89/2*z^90 + 45*z^91 + 91/2*z^92 + 46*z^93 + 93/2*z^94 + 47*z^95 + 95/2*z^96 + 48*z^97 + 97/2*z^98 + 49*z^99 + 99/2*z^100 + O(z^101) The value of f(z) are as follows: f(2) = 1/2 f(3) = 1 f(100) = 99/2 f(n) = (n-1)/2 for n > 1 I hope this solves the problem completely. |
|||||||||||||||
| Demetres
Christofides |
Not necessary to do this.
So
therefore
So f(n)=(n-1)/2 Demetres |
|||||||||||||||
| Panna Lal
Patodia |
Demetres has given elegant and cute solution. |