# applications of second order recurrence relation formula

1. 1.

Recall that the Fibonacci sequence satisfies the recurrence relation

 $f_{n+1}=f_{n}+f_{n-1}.$

Thus, $f_{0}=1$, $A=1$, and $B=1$. Therefore, the theorem yields the following formula for the Fibonacci sequence:

 $f_{n}=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}$
2. 2.

Fix (http://planetmath.org/Fix2) a prime $p$ and define a sequence $s$ by $s_{n}=\tau(p^{n})$, where $\tau$ denotes the Ramanujan tau function. Recall that $\tau$ satisfies

 $\tau(p^{n+1})=\tau(p)\tau(p^{n})-p^{11}\tau(p^{n-1}).$

Thus, $s_{0}=1$, $A=\tau(p)$, and $B=-p^{11}$. Therefore, the theorem yields

 $\tau(p^{n})=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}(-p^{11})^{k}(% \tau(p))^{n-2k}.$

This formula is valid for all primes $p$ and all nonnegative integers $n$.

 Title applications of second order recurrence relation formula Canonical name ApplicationsOfSecondOrderRecurrenceRelationFormula Date of creation 2013-03-22 17:51:46 Last modified on 2013-03-22 17:51:46 Owner Wkbj79 (1863) Last modified by Wkbj79 (1863) Numerical id 8 Author Wkbj79 (1863) Entry type Application Classification msc 11A25 Classification msc 11F11 Classification msc 11B39 Classification msc 11B37 Classification msc 03D20 Related topic FibonacciSequence Related topic RamanujanTauFunction