formula for sequences satisfying second order recurrence relations


Let {sn} be a sequenceMathworldPlanetmath such that there exist constants A,BC with s1=As0 and, for all positive integers n,


Then for all nonnegative integers n, we have


where denotes the floor function and (ar) denotes the binomial coefficientMathworldPlanetmath.


This will be proven by inductionMathworldPlanetmath. Due to the presence of n2, odd n and even n should be considered separately. Thus, there are two base steps:

  • If n=0, then

  • If n=1, then


Now assume that the theoremMathworldPlanetmath holds for all nonnegative integers less than or equal to some positive integer n. We must show that the theorem holds for n+1.

Recall that


We can use the induction hypothesis on sn and sn-1:

sn+1 =As0k=0n2(n-kk)BkAn-2k+Bs0k=0n-12(n-1-kk)BkAn-1-2k

First assume that n is odd. Then the first of the two summations has n2=n-12 terms and the second summation has n+12=n+12 terms. Therefore, we must split off the k=n+12 term from the second summation before combining the two summations:

sn+1 =s0(An+1+k=1n2(n-kk)BkAn+1-2k+k=1n2(n-kk-1)BkAn+1-2k+Bn+12)

Now assume that n is even. Then the two summations have the same number of terms and can be combined as is:

sn+1 =s0(An+1+k=1n+12[(n-kk)+(n-kk-1)]BkAn+1-2k)

Hence, the theorem holds for all nonnegative integers n. ∎

Title formula for sequences satisfying second order recurrence relations
Canonical name FormulaForSequencesSatisfyingSecondOrderRecurrenceRelations
Date of creation 2013-03-22 17:51:43
Last modified on 2013-03-22 17:51:43
Owner Wkbj79 (1863)
Last modified by Wkbj79 (1863)
Numerical id 7
Author Wkbj79 (1863)
Entry type Theorem
Classification msc 11B37
Classification msc 03D20