```

wu :: forums
(http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)

riddles >> putnam exam (pure math) >> Summation
(Message started by: ThudanBlunder on Mar 20th, 2008, 1:00pm)

```

Title: Summation
Post by ThudanBlunder on Mar 20th, 2008, 1:00pm
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(3/5)n*F(n) where F(n) is the nth Fibonacci number.
0

Title: Re: Summation
Post by towr on Mar 20th, 2008, 1:15pm
[hide]Seems like we could just use the closed form for fibonacci numbers
I'll see what I can do after House[/hide]

Title: Re: Summation
Post by towr on Mar 20th, 2008, 1:37pm
[hide]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(3/5)n F(n)
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif[(3/5)n (phin  - (-1/phi)n)/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif5]
1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif5 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif[(3/5 phi)n - (-3/5 1/phi)n]
1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif5 [ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(3/5 phi)n - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(-3/5 1/phi)n ]
1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif5 [ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(3/5 phi)n - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(-3/5 1/phi)n ]
1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif5 [ 1/(1-3/5 phi) - 1/(1+ 3/5 1/phi)]
15[/hide]

Seems like something which might be the answer..

Title: Re: Summation
Post by ThudanBlunder on May 8th, 2008, 9:33pm

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifF(n)/10n+1
1

Title: Re: Summation
Post by towr on May 9th, 2008, 12:37am
You can use the same approach, just replace 3/5 by 1/10 and divide the whole by ten.
[hide]    1/89    [/hide]

In general http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifan F(n) = a/(1 - a - a2) if it converges.

Title: Re: Summation
Post by ThudanBlunder on May 9th, 2008, 10:15am
Ah, I wasn't aware of that formula.

The reason I added the second summation is that we have

n

1 --> 0.01

2 --> 0.001

3 --> 0.0002

4 --> 0.00003

5 --> 0.000005

6 --> 0.0000008

7 --> 0.00000013

etc

0.011235955056179775280898876404494......
which is 1/89, as you say.

I was wondering why 89, but from the formula it is now clear, as we get
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifF(n)/10n+1 = (0.1)2/(1 - 0.1 - 0.01) = 1/89
1

Title: Re: Summation
Post by towr on May 10th, 2008, 1:42am

on 05/09/08 at 10:15:37, ThudanBlunder wrote:
 Ah, I wasn't aware of that formula.
Neither was I, until I worked it out. I had a bit of trouble getting quickmath to simplify it, too.
It's neat though.
And you can probably generalize it further for other second order recurrences. (Although I'm not sure how pretty the result will be; because it has 5 parameters.)

Title: Re: Summation
Post by Eigenray on May 10th, 2008, 11:11am

on 05/10/08 at 01:42:16, towr wrote:
 Neither was I, until I worked it out. I had a bit of trouble getting quickmath to simplify it, too.It's neat though.And you can probably generalize it further for other second order recurrences. (Although I'm not sure how pretty the result will be; because it has 5 parameters.)

5?  But suppose An+2 = a An+1 + b An, and let A(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif Anxn.  What is A(x)*(1 - a x - b x2)?  Of course this works for linear recurrences of any order.

Title: Re: Summation
Post by towr on May 11th, 2008, 7:19am

on 05/10/08 at 11:11:13, Eigenray wrote:
 5?
Yes, the two starting values, the two factors in the recurrence, and the geometric ratio.

Title: Re: Summation
Post by Eigenray on May 11th, 2008, 9:38am

on 05/11/08 at 07:19:42, towr wrote:
 Yes, the two starting values, the two factors in the recurrence, and the geometric ratio.

Can you give an example?

Oh wait, do you mean x?  I was thinking of the generating function itself, which only has 4 parameters.

Title: Re: Summation
Post by towr on May 11th, 2008, 10:04am

on 05/11/08 at 09:38:56, Eigenray wrote:
 Can you give an example?Oh wait, do you mean x?  I was thinking of the generating function itself, which only has 4 parameters.
Yes; after all, you need x as well before you get a value. I suppose one could argue about terminology, but I just deemed everything you need to fill in to get an answer a parameter.