Enumerative Combinatorics · Ordinary generating functions, recurrences, and Catalan numbers

Let a₀=2, a₁=5, and aₙ=5aₙ₋₁-6aₙ₋₂ for n ≥ 2

Problem

Let $a_0=2$, $a_1=5$, and $a_n=5a_{n-1}-6a_{n-2}$ for $n\ge 2$. Derive its ordinary generating function by summing the recurrence with the initial terms explicitly removed. Find a closed formula using partial fractions and explain the relation between the denominator factors and the characteristic roots.

Hint

Write each summed recurrence term with its actual starting index.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

Check your answer See the full solution

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Enumerative Combinatorics sample problem: Try the free sample problem.

More Enumerative Combinatorics practice problems

A group has six distinct volunteersCounting principles, bijections, and the pigeonhole principle
Among n distinct volunteers, a specified set of r volunteers is qualified to serve as…Counting principles, bijections, and the pigeonhole principle
Let a,b ≥ 0 and let k be an integerBinomial and multinomial coefficients, identities, and lattice paths
Let a,b ≥ 0 and h ≥ 1 be integers with b-a<hBinomial and multinomial coefficients, identities, and lattice paths
For n ≥ 1, a positive composition of n is an ordered list of positive integers summing…Compositions, multisets, and distributing objects into boxes
Among thirty labeled projects, eighteen use method A, fourteen use method B, and twelve…Inclusion-exclusion, derangements, and surjections
Let S(n,k) count partitions of [n] into k nonempty unordered blocksSet partitions, Stirling numbers, and the cycle structure of permutations
An integer partition of n is a finite weakly decreasing sequence of positive integers…Integer partitions and Ferrers diagrams
If aₙ counts structures on a specified set of n distinct labels, its exponential…Exponential generating functions and labeled structures