Author |
Topic: Simple Function (Read 600 times) |
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender: 
Posts: 767
|
 |
Simple Function
« on: Mar 2nd, 2004, 11:43am » |
 Quote  Modify
|
1.
f(0) = 1
f(1) = 2
f(n) = f(n-1) - f(n-2), n >= 2
What is f(1,000)?
Hint: f(n) is cyclic
2.
f(0) = a
f(1) = b
f(n) = f(n-1) - f(n-2), n >= 2
What is f(1,000)?
|
| « Last Edit: Mar 2nd, 2004, 11:46am by John_Gaughan » |
 IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Function
« Reply #1 on: Mar 2nd, 2004, 12:33pm » |
Quote Modify
|
::
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
::
note, I do know this is doing it 'the hard way' but it so much more fun 
|
| « Last Edit: Mar 2nd, 2004, 12:44pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Simple Function
« Reply #2 on: Mar 2nd, 2004, 12:44pm » |
Quote Modify
|
towr how did you find that
::
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
::
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Function
« Reply #3 on: Mar 2nd, 2004, 12:47pm » |
Quote Modify
|
on Mar 2nd, 2004, 12:44pm, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Simple Function
« Reply #4 on: Mar 2nd, 2004, 12:56pm » |
Quote Modify
|
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.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Function
« Reply #5 on: Mar 2nd, 2004, 1:01pm » |
Quote Modify
|
on Mar 2nd, 2004, 12:56pm, 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 )
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Simple Function
« Reply #6 on: Mar 2nd, 2004, 1:15pm » |
Quote Modify
|
on Mar 2nd, 2004, 1:01pm, towr wrote:
You could always write a C++ CGI and use std::complex.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Simple Function
« Reply #7 on: Mar 2nd, 2004, 3:22pm » |
Quote Modify
|
on Mar 2nd, 2004, 1:01pm, towr wrote:
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
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Simple Function
« Reply #8 on: Mar 2nd, 2004, 5:48pm » |
Quote Modify
|
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. 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
 
Gender:
Posts: 2873
|
|
Re: Simple Function
« Reply #9 on: Mar 3rd, 2004, 3:30am » |
Quote Modify
|
on Mar 2nd, 2004, 5:48pm, 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. |
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Function
« Reply #10 on: Mar 3rd, 2004, 3:44am » |
Quote Modify
|
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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Simple Function
« Reply #11 on: Mar 3rd, 2004, 1:58pm » |
Quote Modify
|
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 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Simple Function
« Reply #12 on: Mar 3rd, 2004, 7:36pm » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Simple Function
« Reply #13 on: Mar 3rd, 2004, 7:37pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Function
« Reply #14 on: Mar 4th, 2004, 12:03am » |
Quote Modify
|
on Mar 3rd, 2004, 7:36pm, 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
|
| « Last Edit: Mar 4th, 2004, 12:06am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Simple Function
« Reply #15 on: Mar 4th, 2004, 8:25pm » |
Quote Modify
|
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
......[-1 1] [ [omega] 1 ] [ 0 [omega]' ] [ [omega] 1 ],
which means
An = [ 1 [omega] ] [ [omega]n 0 ] [ 1 -[omega] ] (1+[omega])/3
.......[ [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.
|
| « Last Edit: Mar 4th, 2004, 8:32pm by Eigenray » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Simple Function
« Reply #16 on: Mar 5th, 2004, 7:54pm » |
Quote Modify
|
Interesting. Effectively this second approach is the same thing I was doing, but it is a different way of viewing the same underlying calculations.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print