Category Archives: recurrence relations

Solving Second-Order Difference Equations with Constant Coefficients: Part II

In this post we’ll discuss the missing case from last month’s derivation of the solution for second-order difference equations with constant coefficients; namely, the case in which the characteristic equation has a repeated root rather than two distinct roots. Once … Continue reading

Solving Second-Order Difference Equations with Constant Coefficients

Suppose you have a linear, homogeneous second-order difference equation with constant coefficients of the form .  The solution procedure is as follows: “Guess” a solution of the form .  Then substitute this guess into the difference equation to obtain .  … Continue reading

An Explicit Solution to the Fibonacci Recurrence

The Fibonacci sequence is a famous sequence of numbers that starts 1, 1, 2, 3, 5, 8, 13, 21, and continues forever.  Each number in the sequence is the sum of the two previous numbers in the sequence.  It’s easy to … Continue reading

Proof of the Recursive Identity for the Bernoulli Numbers

The Bernoulli numbers satisfy the recursive relationship .  (Here, is the Iverson bracket, where evaluates to 1 if P is true and 0 if P is false.)  The relationship can be used to calculate the Bernoulli numbers fairly easily.  This post gives a … Continue reading

| 1 Comment

Shifts, Finite Differences, and Binomial Transforms

The binomial transform of a sequence is the sequence satisfying  In this post we prove the following: Theorem: If is the binomial transform of , then  In other words, the mth finite difference of is the binomial transform of the shifted sequence . … Continue reading

Solving Two-Term Combinatorial Recurrence Relations, Part II

A few years ago I published a paper [2] giving a partial answer to the following question in Graham, Knuth, and Patashnik’s Concrete Mathematics (Problem 6.92): Develop a general theory of the solutions to the two-parameter recurrence A post from a few years … Continue reading

Posted in combinatorics, recurrence relations | 1 Comment

Solving Two-Term Combinatorial Recurrence Relations

Many named combinatorial numbers satisfy the following general two-term combinatorial recurrence relation: For example: Binomial coefficients: Stirling cycle numbers: Stirling subset numbers: Lah numbers: Eulerian numbers: Second-order Eulerian numbers: It is not known how to solve the recurrence in general. … Continue reading

Posted in combinatorics, recurrence relations | 1 Comment