applications of second order recurrence relation formula

We give two applications of the formula for sequences satisfying second order recurrence relations:

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 }\left(\genfrac{}{}{0pt}{}{n-k}{k}\right)$$

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 }\left(\genfrac{}{}{0pt}{}{n-k}{k}\right){(-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