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

        riddles >> easy >> Simple Function
        
(Message started by: John_Gaughan on Mar 2nd, 2004, 11:43am)
Title: Simple Function
Post by John_Gaughan on Mar 2nd, 2004, 11:43am
1.
f(0) = 1
f(1) = 2
f(n) = f(n-1) - f(n-2), n >= 2

What is f(1,000)?

Hint: [hide]f(n) is cyclic[/hide]

2.
f(0) = a
f(1) = b
f(n) = f(n-1) - f(n-2), n >= 2

What is f(1,000)?
Title: Re: Simple Function
Post by towr on Mar 2nd, 2004, 12:33pm
::[hide]
D = (1)2 + 4*(-1) = -3

l1 = (1 - sqrt(D))/2 = (1 - sqrt(3)i)/2
l2 = (1 + sqrt(D))/2 = (1 + sqrt(3)i)/2

alpha = (a*l2 - b)/(l1*(l2 - l1))
beta = (a*l1 - b)/(l2*(l1 - l2))

f(n) = alpha * l1n + beta * l2n

1)
f(n) = sqrt(3) sin(pi n/3) - cos(pi n/3)
f(1000) = -1

2)
f(n) = sqrt(3)/3 (a + b) sin(pi n/3) + (a - b) cos(pi n/3)
f(1000) = -a
[/hide]::

note, I do know this is doing it 'the hard way' but it so much more fun ;D
Title: Re: Simple Function
Post by Sameer on Mar 2nd, 2004, 12:44pm
towr how did you find that???

:: [hide]

Basically the sequence has a period

1,2,1,-1,-2,-1 keeps on repeating.

Hence the period is 6
so f(n) = f(n+6k)

Thus 1000 = 6*(166) + 4
so f(1000) = f(6*166 + 4) = f(4) = -1

Also
This sequence is same as

a, b, b-a, -a, -b, a-b

Consequently f(1000) = f(4) = -a

[/hide] ::
Title: Re: Simple Function
Post by towr on Mar 2nd, 2004, 12:47pm

on 03/02/04 at 12:44:24, Sameer wrote:
towr how did you find that???
It's a standard way to change a linear recurrence equation into a closed formula.
I think I learned it from Icarus.. (And mathworld)
Title: Re: Simple Function
Post by John_Gaughan on Mar 2nd, 2004, 12:56pm
towr, you just had to go and bring trigonometry into this :-)

Sameer's answer is the one I was looking for, which is what my hint was hinting at.
Title: Re: Simple Function
Post by towr on Mar 2nd, 2004, 1:01pm

on 03/02/04 at 12:56:36, John_Gaughan wrote:
towr, you just had to go and bring trigonometry into this :-)
Well, I suppose I could have left it complex.. ::)

I just wish I could get php to work with imaginary numbers, so my script works for cyclic recurrence equations..
( http://tcw2.ppsw.rug.nl/~towr/PHP/series.php )
Title: Re: Simple Function
Post by John_Gaughan on Mar 2nd, 2004, 1:15pm

on 03/02/04 at 13:01:53, towr wrote:
I just wish I could get php to work with imaginary numbers, so my script works for cyclic recurrence equations..
( http://tcw2.ppsw.rug.nl/~towr/PHP/series.php )

You could always write a C++ CGI and use std::complex.
Title: Re: Simple Function
Post by Sameer on Mar 2nd, 2004, 3:22pm

on 03/02/04 at 13:01:53, towr wrote:
( http://tcw2.ppsw.rug.nl/~towr/PHP/series.php )


Kewl I wonder what these coefficients (|1,|2,alpha and beta) signify.. It is easy to see what sequence I generated:

l1:-0.61803398874989
l2:1.6180339887499
alpha:-0.44721359549996
beta:0.44721359549996

Sn = alpha * l1n + beta * l2n
S3: 2 , 2
S4: 3 , 3
S5: 5 , 5
S6: 8 , 8
S7: 13 , 13
S8: 21 , 21
S9: 34 , 34
S10: 55 , 55
S11: 89 , 89
S12: 144 , 144
S13: 233 , 233
S14: 377 , 377
S15: 610 , 610
S16: 987 , 987
S17: 1597 , 1597
S18: 2584 , 2584
S19: 4181 , 4181
Title: Re: Simple Function
Post by Icarus on Mar 2nd, 2004, 5:48pm
I've been preaching this means of finding formulas for linear recurrence for some time now. I first figured it out for myself, but it was far too obvious to believe I discovered it, and sure enough, you can find it elsewhere.

The basic idea is this: suppose you have a recurrence formula such as
(*) fn = Afn-1 + Bfn-2.

You will also be given initial values, but for now, we want to look at every sequence (integer or not) that satisfies this recurrence.

Note that if {fn} satisfies (*), so does {kfn} for any constant k, and if {gn} also satisfies (*), then so does {fn + gn}. So any linear combination of sequences satisfying (*) also satisfies (*).

Any particular solution is completely determined by its values for n=0 and n=1. This means that the set of all solutions must be a two-dimensional vector space. So if I can find two independent solutions, I can express every solution as a linear combination of these two.

To find solutions, I try something very simple: let fn = rn for some constant r. (*) becomes:
rn = Arn-1 + Brn-2.

Dividing by rn-2 leaves the equation r2 - Ar - B = 0, which generally has two roots r1 and r2.

Hence, I can express any sequence fn that satisfies (*) as
fn = C1 r1n + C2 r2n,

where C1 and C2 are constants. To evaluate them, I look at the equations for n=0 and n=1 (since I am given the values of f0 and f1). This gives 2 equations in 2 unknowns which I can solve for C1 and C2.



For example, the Fibonicci sequence satisfies
f(n) = f(n-1) + f(n-2),

with f(0) = 0, f(1) = 1. So r2 - r - 1 = 0, which has roots r1 = (1 + [surd]5)/2 = [phi]-1, r2 = (1+[surd]5)/2 = -[phi].

0 = f(0) = C1 + C2
1 = f(1) = C1[phi]-1 - C2[phi]
which solves to C1 = 1/[surd]5, C2 = -1/[surd]5.

So we have the well-known formula for the Fibonicci sequence:
fn = ([phi]-n - (-[phi])n)/[surd]5,

where [phi] = ([surd]5 - 1)/2 is the golden ratio.


The process extends in an obvious fashion to higher order reccursions, with the result that you get a higher order polynomial to solve. There is one catch, though. To see it, try finding the formula for this one:

f(n) = 2f(n-1) - f(n-2),  f(0)=1, f(1)=0.


I will also leave it as a challenge what you should do in this case. :D
Title: Re: Simple Function
Post by rmsgrey on Mar 3rd, 2004, 3:30am

on 03/02/04 at 17:48:11, Icarus wrote:
The process extends in an obvious fashion to higher order reccursions, with the result that you get a higher order polynomial to solve. There is one catch, though. To see it, try finding the formula for this one:

f(n) = 2f(n-1) - f(n-2),  f(0)=1, f(1)=0.


I will also leave it as a challenge what you should do in this case. :D

The characteristic polynomial for the sequence is
r2-2r+1==(r-1)2=0
Because of the repeated root, you only find one independent solution this way. It's been 5 years since I covered this briefly at uni (and a year or two more since I first met it), so I can't remember the details for the special cases - specifically the second independent solution.
Title: Re: Simple Function
Post by towr on Mar 3rd, 2004, 3:44am
I think you get something like
A r^n + B n*r^n, and since r = 1
that would make A + B n, with A = 1, B = -1
f(n) = 1 - n
Title: Re: Simple Function
Post by Sameer on Mar 3rd, 2004, 1:58pm
Crap it just struck me.. isn't this standard methods to find the solution to differential equations...

Also we used similar things in DSP i.e. they were discrete in time and hence we had difference functions which is exactly what the problem is.

Education is waste on me  :'(
Title: Re: Simple Function
Post by Eigenray on Mar 3rd, 2004, 7:36pm
We can also use generating functions:
Let f(x) = [sum]n=0[infty]fnxn = a + bx + ...
fn = fn-1 - fn-2
fnxn = fn-1xn - fn-2xn
Summing both sides from n=2 to [infty]:
f(x) - (a+bx) = x( f(x) - a ) - x2 f(x)
f(x) (1-x+x2) = (b-a)x + a
f(x) = ((b-a)x+a)/(1-x+x2),
and fn is the coefficient of xn term.  Let [omega] = e[pi]i/3 = (1 + i[sqrt]3)/2, [omega]' = 1/[omega] = (1-i[sqrt]3)/2, so that 1-x+x2 = (1-[omega]x)(1-x/[omega]).  Using partial fractions, write:
f(x) = ((b-a)x+a)/(1-x+x2) = r/(1-[omega]x) + s/(1-x/[omega]),
r = ((b-a)/[omega]+a)/(1-1/[omega]2) = (b-a+a[omega])/(i[sqrt]3)
s = ((b-a)[omega]+a)/(1-[omega]2) = -(b-a+a/[omega])/(i[sqrt]3)
and the coefficient of xn in this is simply:
fn = r[omega]n + s[omega]-n
= 1/(i[sqrt]3)[(b-a)([omega]n-[omega]-n) + a([omega]n+1-[omega]-n-1)]
= 1/(i[sqrt]3[/sqrt])[(b-a)2isin([pi]n/3) + a2isin([pi](n+1)/3)]
= [(b-a)sin([pi]n/3)+asin([pi](n+1)/3)]/sin([pi]/3),
which we can also write as
[asin([pi](n+2))/3 + bsin([pi]n/3)]/([sqrt]3/2), or
[(a+b)sin([pi](n+1)/3)cos([pi]/3) + (a-b)cos(pi](n+1)/3)sin([pi]/3)]/([sqrt]3)/2), or
(a+b)sin([pi](n+1)/3)[sqrt]3/3 + (a-b)cos([pi](n+1)/3)

(towr, your answer is off by one)
Title: Re: Simple Function
Post by Icarus on Mar 3rd, 2004, 7:37pm
Effectively, the reccurence formula is a discrete version of a homogenous linear differential equation, so it is hardly surprising that the same basic ideas work for both. More generally, the concept of vector spaces of functions is useful for approaching many problems.

Towr is correct: if a root r of the characteristic polynomial is of multiplicity k, then ni rn is a solution for each i [le] k, which provides you with all the independent solutions you need.
Title: Re: Simple Function
Post by towr on Mar 4th, 2004, 12:03am

on 03/03/04 at 19:36:51, Eigenray wrote:
(towr, your answer is off by one)
hmm.. you're right. I must have forgotten to compensate for the fact f(0) and f(1) are given, and not f(1) and f(2)..
So the answers are -2 & -b, not -1 & -a
Title: Re: Simple Function
Post by Eigenray on Mar 4th, 2004, 8:25pm
Here's another method.  Let A be the matrix:
[ 0  1 ]
[-1  1 ],
so that An (a  b)t = (f(n)  f(n+1))t.
To compute An, diagonalize it.  The eigenvalues of A are [omega] = (1+i[sqrt]3)/2, and [omega]'=1/[omega], with eigenvectors (1  [omega])t and ([omega]  1)t, so we have
A = [ 0  1 ] = [ 1  [omega] ] [ [omega]  0 ] [ 1  [omega] ]-1
[hide]......[/hide][-1  1]    [ [omega]  1 ] [ 0  [omega]' ] [ [omega]  1 ],
which means
An = [ 1  [omega] ] [ [omega]n  0 ] [ 1  -[omega] ] (1+[omega])/3
[hide].......[/hide][ [omega]  1 ] [ 0  [omega]-n] [ -[omega]  1 ],
yielding
f(n) = a(2/3)[cos([pi]n/3)+cos([pi](n+1)/3)] + b(2/3)[cos([pi](n-1)/3)-cos([pi](n+1)/3)],
which amounts to the same thing as before.
Title: Re: Simple Function
Post by Icarus on Mar 5th, 2004, 7:54pm
Interesting. Effectively this second approach is the same thing I was doing, but it is a different way of viewing the same underlying calculations.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board