Sunday, August 8, 2010

FT18: Divisibility Properties for the Lucas Numbers

Two other formulas from part 16 contain terms with the factor F(m), and so can be treated similarly to the previous post. These are:

  • F(kn + m) (−1)(n+1)k/2 F (m) (mod L(n)),
    for k even.
  • L(kn+m) (−1)(n+1)(k−1)/2 F(m) L(n−1) (mod L(n)),
    for k odd.

Take m = 0 and use the fact that F(0) = 0 to see that:

  • L(n) | F (kn) for k even.
  • L(n) | L (kn) for k odd.

FT17: Divisibility Properties for the Fibonacci Numbers

Let's look at the first two congruences from the previous section:

  • F(kn + m) (−1)nk/2 F (m) (mod F(n)),
    for k even.
  • F(kn + m) (−1)n(k−1)/2 F (m) F(n−1) (mod F(n)),
    for k odd.

Since F(0) = 0, we can take m = 0 here to see that:

  • n | j implies F(n) | F(j)
(where "x | y" means "y is a multiple of x").

Here's a direct consequence of this:

  • If F(n) is prime, then either n is prime or n=4.


In fact, we can improve on the divisibility property. We'll show that:

  • gcd(F(m), F(n)) = F(gcd(m, n)) for non-zero m and n.

To see this, first observe that it's sufficient to look at positive m and n, since F(−x) = ±F(x).

Also, for x > 1, it's easy to see by induction that F(x−1) and F(x) are relatively prime.

Now, since gcd(m, n) | m and gcd(m, n) | n, the divisibility property above tells us that F(gcd(m, n)) is a common divisor of F(m) and F(n).

To complete the proof, we'll use mathematical induction. If the claim fails, we can let n be the least positive integer for which (*) there exists a positive integer m < n such that F(m) and F(n) have a common divisor d > F(gcd(m, n)).

Divide n by m to write n = qm + r, with 0 ≤ r < m.

Note that r > 0, since if m | n, we already know that there is no such d.

By the congruence for F, we have

F(n) = F (qm + r) ±F(r) or ±F(r) F(m−1) (mod F(m)).

So at least one of the four numbers ±F(r) or ±F(r) F(m−1) is equal to F(n) plus some multiple of F(m).

Since d divides both F(m) and F(n), d also divides at least one of the four numbers ±F(r) or ±F(r) F(m−1).

Now, d and F(m−1) are relatively prime; this is because d divides F(m), which is relatively prime to F(m−1). It follows that d divides F(r).

So we know that 0 < r < m and that d is a common divisor of F(r) and F(m). Also, n = qm+r, so gcd(r, m) = gcd(n, m), and hence that d > F(gcd(r, m)). But this contradicts the choice of n as the least positive number satisfying (*), completing the proof by induction.

Saturday, August 7, 2010

FT16: Summary of Modular Formulas for F(kn+m) and L(kn+m)


  • F(kn + m) (−1)nk/2 F (m) (mod F(n)),
    for k even.
  • F(kn + m) (−1)n(k−1)/2 F (m) F(n−1) (mod F(n)),
    for k odd.
  • L(kn + m) (−1)nk/2 L (m) (mod F(n)),
    for k even.
  • L(kn + m) (−1)n(k−1)/2 L (m) F(n−1) (mod F(n)),
    for k odd.

  • F(kn + m) (−1)(n+1)k/2 F (m) (mod L(n)),
    for k even.
  • 5 F(kn+m) (−1)(n+1)(k−1)/2 L(m) L(n−1) (mod L(n)),
    for k odd.
  • L(kn + m) (−1)(n+1)k/2 L(m) (mod L(n)),
    for k even.
  • L(kn+m) (−1)(n+1)(k−1)/2 F(m) L(n−1) (mod L(n)),
    for k odd.

Friday, August 6, 2010

FT15: F(kn+m) and L(kn+m) mod L(n )

In this section, we look at the remaining four formulas from part 13, reducing them modulo L(n):

  • 5k/2 F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) L(n) j L(n−1)kj, for k even.
  • 5(k+1)/2 F(kn+m)
    = ∑0 ≤ jk (  k   j  ) L( j+m ) L(n) j L(n−1)kj, for k odd.
  • 5k/2 L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) L(n) j L(n−1)kj, for k even.
  • 5(k−1)/2 L(kn+m)
    = ∑0 ≤ jk (  k   j  ) F( j+m ) L(n) j L(n−1)kj, for k odd.

Each term in each of these sums is a multiple of L(n), with the possible exception of the terms with j=0. So we get the following congruences:

  • 5k/2 F (kn + m) F ( m ) L(n−1)k (mod L(n)), for k even.
  • 5(k+1)/2 F(kn+m) L( m ) L(n−1)k (mod L(n)), for k odd.
  • 5k/2 L (kn + m) L ( m ) L(n−1)k (mod L(n)), for k even.
  • 5(k−1)/2 L(kn+m) F( m ) L(n−1)k (mod L(n)), for k odd.

Simplify these using the congruence L(n−1)2 5 (−1)n+1 (mod L(n)):

  • 5k/2 F (kn + m) F (m) (5 (−1)n+1)k/2 (mod L(n)), for k even.
  • 5(k+1)/2 F(kn+m) L(m) L(n−1) (5 (−1)n+1)(k−1)/2 (mod L(n)), for k odd.
  • 5k/2 L (kn + m) L (m) (5 (−1)n+1)k/2 (mod L(n)), for k even.
  • 5(k−1)/2 L(kn+m) F(m) L(n−1) (5 (−1)n+1)(k−1)/2 (mod L(n)), for k odd.

Now, L(n) is relatively prime to every power of 5, so we can conclude:

  • F(kn + m) (−1)(n+1)k/2 F (m) (mod L(n)), for k even.
  • 5 F(kn+m) (−1)(n+1)(k−1)/2 L(m) L(n−1) (mod L(n)), for k odd.
  • L(kn + m) (−1)(n+1)k/2 L(m) (mod L(n)), for k even.
  • L(kn+m) (−1)(n+1)(k−1)/2 F(m) L(n−1) (mod L(n)), for k odd.

FT14: F(kn+m) and L(kn+m) mod F(n )

Next we'll look at the formulas from part 13, but taken modulo F(n) or L(n).

First, though, let's mention a couple of simple formulas which will be useful. Start with the following, which can be proven by mathematical induction.)

  • F(n−1) F(n+1) = F(n)2+(−1)n
  • L(n−1) L(n+1) = L(n)2+5 (−1)n+1

We'll reduce these modulo F(n) and L(n), respectively. Using the fact that F(n−1) F(n+1) (mod F(n)), and similarly for L, we get:

  • F(n−1)2 (−1)n (mod F(n))
  • L(n−1)2 5 (−1)n+1 (mod L(n))


Now, consider the following two formulas from section 13:

  • F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) F(n) j F(n−1)kj
  • L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) F(n) j F(n−1)kj


All the terms in the two sums are multiples of F(n) except possibly for the j=0 term in each.

In consequence, we have the following congruences:

  • F (kn + m) F (m) F(n−1)k (mod F(n))
  • L (kn + m) L (m) F(n−1)k (mod F(n))

Now, applying the congruence above for F(n−1)2, we have:

  • F (kn + m) (−1)nk/2 F (m) (mod F(n)), for k even
  • F (kn + m) (−1)n(k−1)/2 F (m) F(n−1) (mod F(n)), for k odd
  • L (kn + m) (−1)nk/2 L (m) (mod F(n)), for k even
  • L (kn + m) (−1)n(k−1)/2 L (m) F(n−1) (mod F(n)), for k odd

FT13: Summary of Formulas for F(kn+m) and L(kn+m)

The previous two sections covered a variety of formulas for F(kn+m) and L(kn+m); we summarize them here.


Formulas for the Fibonacci numbers:

  • F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) F(n) j F(n−1)kj, for any k.
  • 5k/2 F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) L(n) j L(n−1)kj, for k even.
  • 5(k+1)/2 F(kn+m)
    = ∑0 ≤ jk (  k   j  ) L( j+m ) L(n) j L(n−1)kj, for k odd.


Formulas for the Lucas numbers:

  • L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) F(n) j F(n−1)kj, for any k.
  • 5k/2 L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) L(n) j L(n−1)kj, for k even.
  • 5(k−1)/2 L(kn+m)
    = ∑0 ≤ jk (  k   j  ) F( j+m ) L(n) j L(n−1)kj, for k odd.

FT12: Lucas-Based Formulas for F(kn+m) and L(kn+m)

Let's follow the method of the last section, but using the formula

  • (L(kn−1) + φL(kn))/√5 = (L(n−1) + φL(n))k/√5k

with Lucas numbers, instead of the similar formula with Fibonacci numbers).

Using the binomial formula and the equation φ j = (L( j − 1 ) + φ L ( j )) / √5, we get:

  • 5k/2 (L(kn−1) + φ L(kn))

    = √5 (L(n−1) + φ L(n))k

    = ∑0 ≤ jk (  k   j  )5 φ j L(n) j L(n−1)kj

    = ∑0 ≤ jk (  k   j  ) (L( j−1 ) + φ L( j )) L(n) j L(n−1)kj

    = ∑0 ≤ jk (  k   j  ) L( j−1 ) L(n) j L(n−1)kj  +
           φ ∑0 ≤ jk (  k   j  ) L( j ) L(n) j L(n−1)kj

We'll need to treat this differently based on whether the number k is even or odd.


Case 1: k is even.

If k is even, then 5k/2 is an integer. It follows that, as in part 11, we can apply the fact that a + bβ = c + dβ implies that a = c and b = d if a, b, c, and d are rational and β is irrational, to conclude that the following two formulas must be true:

  • 5k/2 L (kn − 1) = 0 ≤ jk (  k   j  ) L ( j − 1 ) L(n) j L(n−1)kj, for k even
  • 5k/2 L (kn) = 0 ≤ jk (  k   j  ) L ( j ) L(n) j L(n−1)kj, for k even

Combine these two formulas with the basic recurrence relation for the Lucas numbers to yield:

  • 5k/2 L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) L(n) j L(n−1)kj, for k even.

Also, the formula F(x) = (L(x−1) + L(x+1)) / 5 gives us:

  • 5k/2 F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) L(n) j L(n−1)kj, for k even.


Case 2: k is odd.

If k is odd, then 5k/2 is an integer multiple of 5, so it is irrational.

We'll start with the formula 5k/2 (L(kn−1) + φ L(kn)) = 0 ≤ jk (  k   j  ) L( j−1 ) L(n) j L(n−1)kj +
φ ∑0 ≤ jk (  k   j  ) L( j ) L(n) j L(n−1)kj, from right before we split into two cases.

Multiply by 2φ−1 = 5 and use the fact that φ √5 = φ + 2 to yield:

  • 5(k+1)/2 (L(kn−1) + φ L(kn))

    = (2φ−1) ∑0 ≤ jk (  k   j  ) L( j−1 ) L(n) j L(n−1)kj  +
           (φ+2) ∑0 ≤ jk (  k   j  ) L( j ) L(n) j L(n−1)kj

    = ∑0 ≤ jk (  k   j  ) (2 L( j ) − L( j−1 )) L(n) j L(n−1)kj  +
     φ ∑0 ≤ jk (  k   j  ) (2 L( j−1 ) + L( j ) )L(n) j L(n−1)kj

    = ∑0 ≤ jk (  k   j  ) 5 F( j−1 ) L(n) j L(n−1)kj  +
           φ ∑0 ≤ jk (  k   j  ) 5 F( j ) L(n) j L(n−1)kj

Since we're assuming that k is odd, 5(k+1)/2 is an integer, and, dividing by 5, it follows that:

  • 5(k−1)/2 L(kn−1)
    = ∑0 ≤ jk (  k   j  ) F( j−1 ) L(n) j L(n−1)kj

and

  • 5(k−1)/2 L(kn)
    = ∑0 ≤ jk (  k   j  ) F( j ) L(n) j L(n−1)kj.

We can apply the recurrence relations for F and L to conclude that:

  • 5(k−1)/2 L(kn+m)
    = ∑0 ≤ jk (  k   j  ) F( j+m ) L(n) j L(n−1)kj,
    for k odd.

Finally, using the facts that 5F(x) = L(x−1) + L(x+1) and L(x) = F(x−1) + F(x+1), we have:

  • 5(k+1)/2 F(kn+m)
    = ∑0 ≤ jk (  k   j  ) L( j+m ) L(n) j L(n−1)kj,
    for k odd.

FT11: Fibonacci-Based Formulas for F(kn+m) and L(kn+m)

In the last section, we derived the following form of our analogue to de Moivre's theorem:

  • F(kn−1) + φ F(kn) = (F(n−1) + φ F(n))k

Expanding the expression on the right with the binomial formula, applying the equation φ j = F( j − 1 ) + φ F ( j ), and then using the fact that a + bβ = c + dβ implies that a = c and b = d if a, b, c, and d are rational and β is irrational, one obtains the following two formulas:

  • F (kn − 1) = 0 ≤ jk (  k   j  ) F ( j − 1 ) F(n) j F(n−1)kj
  • F (kn) = 0 ≤ jk (  k   j  ) F ( j ) F(n) j F(n−1)kj

Combine these two formulas with the basic recurrence relation for the Fibonacci numbers to yield:

  • F (kn + m) = 0 ≤ jk (  k   j  ) F ( j + m ) F(n) j F(n−1)kj

Using the fact that L(x) = F(x−1) + F(x+1), we can also see that:

  • L (kn + m) = 0 ≤ jk (  k   j  ) L ( j + m ) F(n) j F(n−1)kj

FT10: More on the de Moivre Analogue

In part 9, we looked at an analogue to de Moivre's theorem. Slightly rephrased, we saw that:

  • L(n)/2 + √5 F(n)/2 = φn

so that:

  • L(kn)/2 + √5 F(kn)/2 = (L(n)/2 + √5 F(n)/2)k.

However, we would like to eliminate the factors of ½, since, when we derive other formulas from these, the ½'s end up obscuring which numbers are integers.

We'll actually do this in two ways, one using the Fibonacci numbers and one using the Lucas numbers.

Taking the formula φn = L(n)/2 + √5 F(n)/2, rewriting 5 as 2φ − 1, and using the fact that L(n) = 2F(n−1) + F(n) yields:

  • φn = F(n−1) + φ F(n)

Similarly, but using the fact that F(n) = (2L(n−1) + L(n))/5, we get:

  • φn = (L(n−1) + φL(n))/√5

Alternatively, one can prove these two formulas for φn by mathematical induction.

Plugging these expressions into the formula n)k = φnk results in two more forms of our analogue to de Moivre's theorem:

  • F(kn−1) + φ F(kn) = (F(n−1) + φ F(n))k
  • (L(kn−1) + φL(kn))/√5 = (L(n−1) + φL(n))k/√5k

Next we'll look at some applications of these formulas.

FT9: de Moivre's Formula

In this section, we look at the analogue to de Moivre's formula, cos kx + i sin kx = (cos x + i sin x)k.

Let n be any integer. We know that L(n) + √5 F(n) = 2 φn.

It follows that, for any non-negative integer k:

  • L(kn) + √5 F(kn) = (L(n) + √5 F(n))k / 2k—1


If k is positive, we can expand this using the binomial theorem. Then, applying the fact that a + bβ = c + dβ implies that a = c and b = d if a, b, c, and d are rational and β is irrational, we can derive the following two formulas:

  • 2k—1 L(kn) = 0 ≤ j ≤ [k/2] (  k j ) 5 j F(n) 2j L(n) k—2j
  • 2k—1 F(kn) = 0 ≤ j ≤ [(k—1)/2] (      k     j + 1 ) 5 j F(n)2j+1 L(n)k—2j—1

Note: [x] here denotes the greatest integer less than or equal to x.

However, the factor 2k—1 here gets in the way, and we'll come up with more useful versions of these formulas in the next section.

Tuesday, July 27, 2010

FT8: Recurrence Relations for Ftan and Fcot

This is the eighth in a series of posts on Fibonacci trigonometry:

Part 1: Basic Definitions

Part 2: The Canonical Basis and Closed-Form Expressions

Part 3: The Basic Analogies

Part 4: Fibonacci Formulas Using sinh, etc. — Real Number Version

Part 5: Fibonacci Formulas Using sinh, etc. — Complex Number Version

Part 6: Trigonometric-Style Identities

Part 7: The Fibonacci Tangent and Cotangent Functions

Part 8: Recurrence Relations for Ftan and Fcot

 

The addition formulas for Ftan and Fcot give us the following recurrence relations:

  • 5 Ftan(n + 1) = 1 + 4 / (1 + 5 Ftan(n))
  • Fcot(n + 1) = 1 + 4 / (1 + Fcot(n))

These recurrence relations yield continued-fraction-style expansions for Ftan(n) and Fcot(n).

Now, as n approaches infinity, Ftan(n) approaches 1/√5, and Fcot(n) approaches √5. These facts can be seen either from the continued-fraction expansions or from the earlier formulas involving φ.

FT7: Fibonacci Tangent and Cotangent Functions

This is the seventh in a series of posts on Fibonacci trigonometry:

Part 1: Basic Definitions

Part 2: The Canonical Basis and Closed-Form Expressions

Part 3: The Basic Analogies

Part 4: Fibonacci Formulas Using sinh, etc. — Real Number Version

Part 5: Fibonacci Formulas Using sinh, etc. — Complex Number Version

Part 6: Trigonometric-Style Identities

Part 7: The Fibonacci Tangent and Cotangent Functions

Part 8: Recurrence Relations for Ftan and Fcot

 

Recall that, since F behaves analogously to the sine function, and L to the cosine function, we followed the usual development of trigonometry by defining:

  • Ftan(n) = F(n) / L(n), the Fibonacci tangent function
  • Fcot(n) = L(n) / F(n), the Fibonacci cotangent function (for n ≠ 0)
  • Fsec(n) = 1 / L(n), the Fibonacci secant function
  • Fcsc(n) = 1 / F(n), the Fibonacci cosecant function (for n ≠ 0)

We'll continue to use the notation F and L, since those symbols are standard, rather than using Fsin and Fcos, respectively.

Just as 1 + tan2x = sec2x and 1 + cot2x = csc2x, we have:

  • 1 – 5 Ftan(x)2 = 4 (–1)x Fsec(x)2
  • Fcot(x)2 – 5 = 4 (–1)x Fcsc(x)2, for x ≠ 0

Ftan and Fcot are odd functions:

  • Ftan(–x) = –Ftan(x)
  • Fcot(–x) = –Fcot(x), for x ≠ 0

Fsec and Fcsc have the same opposite-sign properties as L and F:

  • Fsec(–x) = (–1)x Fsec(x).
  • Fcsc(–x) = (–1)x+1 Fcsc(x), for x ≠ 0

There are addition, subtraction, and double-argument formulas (the formulas for Fcot only apply where the indicated function values are defined, of course):

  • Ftan(x ± y) = (Ftan(x) ± Ftan(y)) / (1 ± 5 Ftan(x) Ftan(y))
  • Fcot(x ± y) = (5 ± Fcot(x) Fcot(y)) / (Fcot(x) ± Fcot(y))
  • Ftan(2x) = 2 Ftan(x) / (1 + 5 Ftan(x)2)
  • Fcot(2x) = (5 + Fcot(x)2) / (2 Fcot(x))

FT6: Trigonometric-Style Identities for the Fibonacci and Lucas Numbers

This is the sixth in a series of posts on Fibonacci trigonometry:

Part 1: Basic Definitions

Part 2: The Canonical Basis and Closed-Form Expressions

Part 3: The Basic Analogies

Part 4: Fibonacci Formulas Using sinh, etc. — Real Number Version

Part 5: Fibonacci Formulas Using sinh, etc. — Complex Number Version

Part 6: Trigonometric-Style Identities

Part 7: The Fibonacci Tangent and Cotangent Functions

Part 8: Recurrence Relations for Ftan and Fcot

 

The Fibonacci numbers and Lucas numbers obey many identities analogous to the trigonometric and hyperbolic identities, with F playing the role of sin or sinh, and L playing the role of cos or cosh. These can be proven either via the closed-form expressions or by mathematical induction.

For example, analogous to the Pythagorean formula sin2x + cos2x = 1, we have:

  • L(x)2 – 5 F(x)2 = 4 (–1)x


Analogous to the double-angle formulas sin 2x = 2 sin x cos x and cos 2x = cos2x - sin2x, we have:

  • F(2x) = F(x) L(x)
  • 2 L(2x) = 5 F(x)2 + L(x)2


There are addition formulas, corresponding to the standard trig formulas sin(x + y) = sin x cos y + cos x sin y and cos(x + y) = cos x cos y - sin x sin y:

  • 2 F(x + y) = F(x) L(y) + F(y) L(x)
  • 2 L(x + y) = 5 F(x) F(y) + L(x) L(y).


Unlike sine and cosine, the functions F and L aren't odd or even, but they do have opposite sign behavior in the following sense:

  • F(–x) = (–1)x+1 F(x)
  • L(–x) = (–1)x L(x).


You can combine the above to get subtraction formulas:

  • 2 F(xy) = (-1)y (F(x) L(y) – F(y) L(x))
  • 2 L(xy) = (-1)y (L(x) L(y) – 5 F(x) F(y))


Product formulas can be derived from the addition and subtraction formulas:

  • 5 F(x) F(y) = L(x + y) + (–1)y+1L(xy)
  • L(x) L(y) = L(x + y) + (–1)yL(xy)
  • F(x) L(y) = F(x + y) + (–1)yF(xy)


Here are a couple of formulas just involving the traditional Fibonacci numbers:

  • F(2x)2 = F(x)2 (5 F(x)2 + 4 (-1)x)
  • F(3x) = F(x) (5 F(x)2 + 3 (-1)x)

... and just involving the Lucas numbers:

  • L(2x) = L(x)2 + 2 (-1)x+1
  • L(3x) = L(x) (L(x)2 + 3 (-1)x+1)


By the way, the formulas for F(2x), F(3x), and L(3x) show that F(x) divides F(2x) and F(3x), and that L(x) divides L(3x). We'll see later on that these are specific examples of general divisibility properties.

FT5: Formulas using Complex Hyperbolic Functions

This is the fifth in a series of posts on Fibonacci trigonometry:

Part 1: Basic Definitions

Part 2: The Canonical Basis and Closed-Form Expressions

Part 3: The Basic Analogies

Part 4: Fibonacci Formulas Using sinh, etc. — Real Number Version

Part 5: Fibonacci Formulas Using sinh, etc. — Complex Number Version

Part 6: Trigonometric-Style Identities

Part 7: The Fibonacci Tangent and Cotangent Functions

Part 8: Recurrence Relations for Ftan and Fcot

 

In part 4, we saw formulas for the Fibonacci numbers and related sequences in terms of the hyperbolic functions. Here we'll see how, by using complex numbers, we can avoid splitting into even and odd cases.

Let ψ = ln φ + πi/2. (Anything that differs from this by an integer multiple of 2πi will also work.)

Then:

  • F(n) = 2 sinh(nψ) / (√5 in)
  • L(n) = 2 cosh(nψ) / in
  • Ftan(n) = tanh(nψ) / √5 
  • Fcot(n) = 5 coth(nψ) 
  • Fsec(n) = in sech(nψ) / 2
  • Fcsc(n) = 5 in csch(nψ) / 2

FT4: Formulas using Real Hyperbolic Functions

This is the fourth in a series of posts on Fibonacci trigonometry:

Part 1: Basic Definitions

Part 2: The Canonical Basis and Closed-Form Expressions

Part 3: The Basic Analogies

Part 4: Fibonacci Formulas Using sinh, etc. — Real Number Version

Part 5: Fibonacci Formulas Using sinh, etc. — Complex Number Version

Part 6: Trigonometric-Style Identities

Part 7: The Fibonacci Tangent and Cotangent Functions

Part 8: Recurrence Relations for Ftan and Fcot

 

So we've seen that the Fibonacci and Lucas sequences have properties analogous to sin and cos, or sinh and cosh. But does this go beyond an analogy to an actual connection? Can we write F in terms of sin or sinh, etc.?

Yes. Here's one way...

We'll write these expressions using hyperbolic functions.

F(n) =

  • 2 sinh (n ln φ) / √5, if n is even,
  • 2 cosh (n ln φ) / √5, if n is odd.

L(n) =

  • 2 cosh (n ln φ), if n is even,
  • 2 sinh (n ln φ), if n is odd.

Ftan(n) =

  • 2 tanh (n ln φ) / √5, if n is even,
  • 2 coth (n ln φ) / √5, if n is odd.

Fcot(n) =

  • 5 coth (n ln φ) / 2, if n is even,
  • 5 tanh (n ln φ) / 2, if n is odd.

Fsec(n) =

  • sech (n ln φ) / 2, if n is even,
  • csch (n ln φ) / 2, if n is odd.

Fcsc(n) =

  • 5 csch (n ln φ) / 2, if n is even,
  • 5 sech (n ln φ) / 2, if n is odd.

In the next section, we'll see how we can use complex numbers in the formulas to avoid splitting into even and odd cases.

FT3: The Basic Analogies


This is the third in a series of posts on Fibonacci trigonometry:








 
In part 2, we gave the following closed-form expressions for the Fibonacci numbers and the Lucas numbers:
  • F(n) = (φn – (–φ)–n)/√5
  • L(n) = φn + (–φ)–n
(Recall that φ represents the golden ratio (1 + √5)/2 = 1.618....)
Using the formulas above, we can derive the following:
  • L(n) + √5 F(n) = 2 φn
  • L(n) – √5 F(n) = 2 (–φ)–n
The four formulas above are reminiscent of standard formulas relating the trigonometric and hyperbolic functions to the exponential function:
F(n) = (φn – (–φ)–n)/√5
L(n) = φn + (–φ)–n

L(n) + √5 F(n) = 2 φn
L(n) – √5 F(n) = 2 (–φ)–n
sin x = (eixe–ix)/2i
cos x = (eix + e–ix)/2
 

cos x + i sin x = eix
cos xi sin x = eix
sinh x = (exe–x)/2
cosh x = (ex + e–x)/2

cosh x + sinh x = ex
cosh x – sinh x = ex

  Because of these similarities, the Fibonacci and Lucas numbers obey many identities similar to well-known trigonometric and hyperbolic identities, as we'll see.
In fact, as we'll see in part 5, there are formulas for F(n) and L(n) in terms of sinh and cosh: F(n) and L(n) are constant multiples of sinh(nψ) and cosh(nψ), respectively, with the proper choice of ψ.





FT2: The Canonical Basis & Closed-Form Expressions

This is the second in a series of posts on Fibonacci trigonometry:

Part 1: Basic Definitions

Part 2: The Canonical Basis and Closed-Form Expressions

Part 3: The Basic Analogies

Part 4: Fibonacci Formulas Using sinh, etc. — Real Number Version

Part 5: Fibonacci Formulas Using sinh, etc. — Complex Number Version

Part 6: Trigonometric-Style Identities

Part 7: The Fibonacci Tangent and Cotangent Functions

Part 8: Recurrence Relations for Ftan and Fcot

 

If u satisfies the equation 1 + u = u2, then the function that maps n to un is a generalized Fibonacci sequence. We'll call this function u*.

There are two solutions to the equation 1 + u = u2: φ = (1 + √5)/2 = 1.618... (the "golden ratio"), and φ' = 1–φ = –1/φ = (1 – √5)/2 = -0.618....

One can see that any generalized Fibonacci function can be written in the form a φ* + b φ'* for uniquely determined constants a and b.

In other words, {φ*, φ'*} is a basis for the vector space of generalized Fibonacci functions (under the naturally defined pointwise operations).

This gives us a closed-form expression for any generalized Fibonacci function f: Take a = (–φ' f (0) + f (1))/√5 and b = f (0) – f (1))/√5. Then f (n) = a φ* (n) + b φ'* (n) for every integer n.

For our purposes, it's useful to rewrite a φ*(n) + b φ'*(n) as a φn + b (–φ)–n.

In particular, the standard Fibonacci and Lucas sequences can be written as follows:

  • F(n) = (φn – (–φ)–n)/√5
  • L(n) = φn + (–φ)–n
Note that I haven't tried to normalize these in any sense, since I wanted to keep the standard integer-valued functions.

Fibonacci Trigonometry 1: Basic Definitions

This is the first in a series of posts on Fibonacci trigonometry:

Part 1: Basic Definitions

Part 2: The Canonical Basis and Closed-Form Expressions

Part 3: The Basic Analogies

Part 4: Fibonacci Formulas Using sinh, etc. — Real Number Version

Part 5: Fibonacci Formulas Using sinh, etc. — Complex Number Version

Part 6: Trigonometric-Style Identities

Part 7: The Fibonacci Tangent and Cotangent Functions

Part 8: Recurrence Relations for Ftan and Fcot

Part 9: Analogue to de Moivre's Formula

Part 10: More on the de Moivre Analogue

Part 11: Fibonacci-Based Formulas for F(kn+m) and L(kn+m)

Part 12: Lucas-Based Formulas for F(kn+m) and L(kn+m)

Part 13: Summary of Formulas for F(kn+m) and L(kn+m)

Part 14: F(kn+m) and L(kn+m) mod F(n)

Part 15: F(kn+m) and L(kn+m) mod L(n)

Part 16: Summary of Modular Formulas for F(kn+m) and L(kn+m)

Part 17: Divisibility Properties for the Fibonacci Numbers

Part 18: Divisibility Properties for the Lucas Numbers

 

I think a connection between the Fibonacci numbers and trigonometry qualifies as a mathematical curiosity. It turns out that the Fibonacci numbers and Lucas numbers obey many identities analogous to the trigonometric and hyperbolic identities, with the Fibonacci numbers playing the role of sin or sinh, and the Lucas numbers playing the role of cos or cosh.

A generalized Fibonacci sequence is a complex-valued function f defined on the set of integers with the property that:

  • f (n + 2) = f (n) + f (n + 1) , for every integer n.


A generalized Fibonacci sequence f is determined by the values of f(0) and f(1) (or indeed by any two values).

The Fibonacci sequence F is defined to be the generalized Fibonacci sequence with F(0) = 0 and F(1) = 1.

The Lucas sequence L is defined to be the generalized Fibonacci sequence with L(0) = 2 and L(1) = 1.


As we'll see, F behaves analogously to the sine function, and L to the cosine function. So let's also define:

  • Ftan(n) = F(n) / L(n), the Fibonacci tangent function
  • Fcot(n) = L(n) / F(n), the Fibonacci cotangent function
  • Fsec(n) = 1 / L(n), the Fibonacci secant function
  • Fcsc(n) = 1 / F(n), the Fibonacci cosecant function

We could write Fsin instead of F, and Fcos instead of L, but we prefer to keep the traditional names F and L for the Fibonacci and Lucas sequences.

F(n) is zero only at n = 0, and L(n) is never zero. It follows that Ftan(n) and Fsec(n) are defined for every integer n, and Fcot(n) and Fcsc(n) are defined for every integer n except 0.


Using mathematical induction, it's easy to prove the following facts:

  • L(n) = F(n−1) + F(n+1) = 2F(n+1) − F(n)
  • 5F(n) = L(n−1) + L(n+1) = 2L(n+1) − L(n)

Also, observing that the sequence of Lucas numbers modulo 5 consists simply of the numbers 2, 1, 3, 4 repeated forever in both directions, we note that:

  • No Lucas number is a multiple of 5.

Friday, July 16, 2010

A Function Whose Zeros Are the Fibonacci Numbers

Here's a function with zeros at precisely the Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, ....

(Click on the image for the full-sized graph.)

This function is defined for all real x ≥ √0.8 = 0.894427....

Incidentally, 1 appears twice in the Fibonacci sequence, and you can see the double zero at x = 1 in the graph.

Thursday, July 15, 2010

An Upside-Down Pascal's Triangle

Take Pascal's triangle, but instead of putting ( nk ) in each entry, put the reciprocal of  (n + 1( nk ).

Then each number is the sum of the two numbers below it:

                1
           1/2     1/2
       1/3     1/6     1/3
   1/4    1/12    1/12    1/4
1/5   1/20    1/30    1/20   1/5
        ... and so on.

I think it's a bit surprising that there's an addition formula for reciprocals at all.