Conference rusure::math

Well, there's 
             F(x+y)F(x-y) = F(x)F(x) + F(y)F(y) - 1  (cosine)
             F(x+y)F(x-y) = F(x)F(x) - F(y)F(y)      (sine, or identity)

Is that the sort of thing you have in mind?

    from 545.5, another functional equation:
    
    	F(x+y) = F(x-1)*F(y) + F(x)*F(y+1)
    
    In this case, F(x) = x'th Fibonnaci number.
    
    len.
    

     re .2,
     
     What if x and y are arbitrary real numbers and not just
     integers?  There is a formula for the n-th Fibonacci number
     that involves n and lots of sqrt(5)'s.   If you plug in a
     real x instead of just an integer n, you can treat this as a
     definition of the Fibonacci function on the reals (it will
     even be continuous).  Will the functional equation then
     still be true for all x and y?
     
     Dan
     

     The following uses a standard technique of solving linear
     recurrences.
     
     If you set F(n) = r^n, then F(n+2) = F(n+1) + F(n) becomes
     r^(n+2) = r^(n+1) + r^n, which after dividing out r^n and
     shuffling terms around yields r^2 - r - 1 = 0.  Call the
     roots of this r1 and r2, then F(n) = c1 r1^n + c2 r2^n.
     Now plug in F(0) = 0 and F(1) = 1 to compute c1 and c2.
     The result is that r1 is the Golden Mean (1 + sqrt(5))/2;
     r2 = -1/r1 = -(r1 - 1); c1 = 1/sqrt(5); c2 = -1/sqrt(5).
     
     The extension of the Fibonacci function to the reals is then
     F(x) = c1 r1^x + c2 r2^x.  However, this involves raising
     negative numbers to non-integral powers, so this is more
     appropriately an extension to the complex numbers.
     
     Dan

.5>     If you set F(n) = r^n, then F(n+2) = F(n+1) + F(n) becomes
    
    I don't understand how you can blithely assume the existence of an r
    that satisfies F(n) = r^n.  Isn't something awry here?
    
      John

     re .7
     
     You could think of it as a trial solution that works.  You
     can prove by induction that the resulting formula is
     correct.  I also know at least three other ways get the same
     result from a linear recurrence like this.  I don't know by
     whom or when or how the methods were first developed.
     
     Dan

    The Fibonacci recurrance is defined by a linear shift operator.  Just look
    at its eigenfunctions, and you'll get the well-known expressions
    for a given set of initial conditions.

    Away from the integers, on the positive real line you get the
    superposition of a logarithmic spiral (which crosses the real axis
    at integer values of the argument) and an exponentially increasing
    transient.

    - Jim

    re .8
    
    Right in that you don't have to "prove" the technique as long as you
    can validate the solution.  The question I failed to ask is:  what is
    the r for which F(n) = r^n?  (Or should I say "z" instead of "r")?
    
      John

     The two roots were r = (1+sqrt(5))/2 and (1-sqrt(5))/2.
     
     Is that what you meant?
     
     Dan

I was looking for a number, r, satisfying F(n) = r^n where F(n) is the
nth Fibonacci number.

Clearly       r = (1+sqrt(5))/2 and (1-sqrt(5))/2.  doesn't work.

So is there _really_ an r that works?  If so what is it?

Curious

The r values provide solutions to the recurrence relation.  To solve the
recurrence relation for a particular set of boundary conditions, a linear
combination of solutions is used.  Does the following help?

Q:  Find some solutions to the recurrence: F(n+2) = F(n+1) + F(n)

A#1:  F(n) = 0
A#2:  F(n) = ((1+sqrt(5))/2)^n
A#3:  F(n) = ((1-sqrt(5))/2)^n
A#4:  F(n) = linear combination of any other solutions

Q:  What is the most general solution to the recurrence: F(n+2) = F(n+1) + F(n)?

A:  F(n) = a * r1^n + b * r2^n, where r1 = (1+sqrt(5))/2, r2 = (1-sqrt(5))/2,
    and a and b are arbitrary.  We justify this claim by noting that F(n) is
    completely determined (for integral n) by the values of F(0) and F(1) alone
    (these are called the 'boundary conditions' of the recurrence), and given
    F(0) and F(1), we show how to choose the values of a and b.

    We solve the following equations:

	F(0) = a + b
	F(1) = a*r1 + b*r2

    for a and b, giving:

	a = (r2*F(0) - F(1))/(r2-r1)
	b = (r1*F(0) - F(1))/(r1-r2)

    Thus, given any values of F(0) and F(1), we can find values of a and b
    so that F(n) = a*r1^n + b*r2^n satisfies the recurrence and the boundary
    conditions.  Since the recurrence and the boundary conditions uniquely
    determine the function (for integer n), we've found the most general
    solution.

     There is another thing to know when using this method; it is
     how to handle multiple roots.  For example, if the
     polynomial in r resulted in the roots
     
          r1, r2, r2, r2, r3, r4, r4
     
     then the solutions will be linear combinations of
     
          r1^n
     
          r2^n
          n r2^n
          n^2 r2^n
     
          r3^n
          r4^n
     
          n r4^n
     
     Each next duplicated root gets multiplied by another factor
     of n.  You can check this by taking a second degree solution
     with distinct roots r1 and r2, and then considering what
     happens in the limit as r1 -> r2.
     
     Dan
     

>> .0     F(x+y)F(x-y) = (F(x)-F(y))^2
     
     Well, in fields of characteristic two, i.e., where 1+1=0,
     let F(x) = x.
                                              
     Then the left hand side is (x+y)(x-y) = x^2 - y^2 = x^2 + y^2
     and the right hand side is (x-y)^2 = x^2 + y^2.
     
     :-)
     
     Also, the above is satisfied by the zero function, and
     F(x*x) = F(x) is satisfied by any constant function.
     
     Who wants to get tackle to F(x+y) + F(x-y) = 2F(x)F(y)?
     
     Dan
     

    Suppose one has two functions continuous on the unit interval
    which commute under functional composition:

		f(g(x)) = g(f(x)),   0 <= x <= 1

    Do these functions always have at least one fixed point?

    - Jim

     re .17
     
     If the range is contained in [0, 1] then both functions will
     have a fixed point, whether they commute or not.  If the
     range is the real line, then they do not have to have fixed
     points; for example f(x) = g(x) = 5 or f(x) = x + c1 and
     g(x) = x + c2, where c1 + c2 is nonzero.
     
     Dan

>> .0     F(x+y)F(x-y) = (F(x)-F(y))^2
    
                    2
How about F(x) = sin (x)?

     re .19
                                           2
     Very good.  I verified that F(x) = sin  (x) works.
     
     How did you figure that out?
     
     Dan

>> .0     F(x+y)F(x-y) = (F(x)-F(y))^2

Letting x=y, we have F(2x)F(0) = 0, so F is identically 0 (this is one
solution), or F(0) = 0.  We'll assume below that F is not identically 0.

We also note that if F(x) = G(x) is a solution, then so is F(x) = B * G(x).

Letting x=0, we see that F(-y) = F(y).

Assume w.l.g. that F(A) > 0.  Then for any z, let x=(z+A)/2, y = (z-A)/2,
and so F(z)F(A) = (F(x)-F(y))^2.  Then F(z) >= 0 for all z.

Are there any other places where F(x) = 0?  With some work we see that, if
F(Z) = 0, then F(k*Z) = 0 for any integer k, and F(Z+x) = F(Z-x).  Thus,
if there are any other zeroes of F, F is a cyclic function.

Etc, etc.