Recurrences and generating functions

The app solves linear recurrences with constant coefficients of any order by the characteristic equation – multiple and complex roots too (the complex form of the solution and its conversion to the real one by de Moivre's theorem) – and with a right side of the form P(n)·qⁿ (also cos nφ, sin nφ, resonance and a sum of right sides). The initial conditions determine the constants; as a check, the app computes further terms from the recurrence and compares them with the formula.

The “Method” chip offers the generating function too (A(x) = Σ aₙxⁿ, partial fractions, geometric series), matrix powers (diagonalization) or, for the first order, summing. A first-order recurrence with a variable coefficient (aₙ₊₁ = (n + 1)aₙ) is solved by a product (factorials), convertible nonlinear recurrences by the substitution bₙ = 1/aₙ or bₙ = ln aₙ. A system of two recurrences is solved by eliminating one sequence or by the matrix, a divide-and-conquer recurrence T(n) = aT(n/b) + f(n) by n = bᵏ – with the master theorem's estimate.

With the “Generating function” operation the app finds the generating function of a sequence given by a formula (n² + 2ⁿ) or by its first terms (1, 0, 1, 0, …), and conversely the formula for aₙ from a function A(x). The number of non-negative whole solutions of x₁ + x₂ + … = N (also with bounds or coefficients – paying with coins) is the coefficient of a generating function.

The graph shows the terms of the sequence as points (both sequences of a system).

How to enter it

`a(n+2) = 5a(n+1) - 6a(n), a(0) = 1, a(1) = 4`	Brackets, the conditions after a comma.
`a_{n+2} = 5a_{n+1} - 6a_n`	Subscripts (also from a photo). Without conditions: the general solution with constants C₁, C₂.
`F_n = F_{n-1} + F_{n-2}, F_1 = F_2 = 1`	The index may go down (aₙ₋₁, aₙ₋₂); one value can be given to several terms.
`a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0`	A system – the equations on lines, the conditions on the last one.
`T(n) = 2T(n/2) + n, T(1) = 1`	Divide and conquer – a term at n/b.
`n^2 + 2^n`	A sequence's formula with the “Generating function” operation (also aₙ = …).
`1, 0, 1, 0, ...`	The first terms separated by commas.
`1/(1 - x - x^2)`	A generating function in x (also A(x) = …) – the formula for aₙ.
`number of solutions x_1 + x_2 + x_3 = 10, x_1 <= 3`	The number of non-negative whole solutions with bounds.

Examples

Two distinct real roots, the check by further terms.

Input: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

The Fibonacci sequence – Binet's formula.

Input: F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$ $F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

Complex roots 1 ± i – the complex form and de Moivre's theorem.

Input: a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

The right side n, a double root 2.

Input: a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

The same recurrence by the generating function.

Input: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Generating function

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

The same recurrence by matrix powers.

Input: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Matrix powers

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

A first-order recurrence by summing.

Input: a_{n+1} = 2a_n + 1, a_0 = 0 Summing

$a_{n+1} = 2a_n + 1, a_0 = 0$

$a_{n+1} = 2a_n + 1, a_0 = 0$ $a_{n+1} = 2a_n + 1, a_0 = 0$

A variable coefficient – the product gives a factorial.

Input: a_{n+1} = (n+1)a_n, a_0 = 1

$a_{n+1} = (n+1)a_n, a_0 = 1$

$a_{n+1} = (n+1)a_n, a_0 = 1$ $a_{n+1} = (n+1)a_n, a_0 = 1$

A nonlinear recurrence – the substitution bₙ = 1/aₙ.

Input: a_{n+1} = a_n/(1 + a_n), a_0 = 1

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$

A system of two recurrences by eliminating the sequence bₙ.

Input:

a_{n+1} = a_n + 2b_n
b_{n+1} = 3a_n + b_n
a_0 = 1, b_0 = 0

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

Divide and conquer (merge sort) – n = 2ᵏ and the master theorem.

Input: T(n) = 2T(n/2) + n, T(1) = 1

The generating function of the sequence n² + 2ⁿ.

Input: n^2 + 2^n Generating function

The formula for aₙ from a generating function – partial fractions by irrational roots.

Input: 1/(1 - x - x^2) Generating function

The number of solutions of x₁ + x₂ + x₃ = 10 with x₁ ≤ 3.

Input: number of solutions x_1 + x_2 + x_3 = 10, x_1 <= 3

počet řešení x_1 + x_2 + x_3 = 10, x_1 <= 3

Known limitations

Not yet: higher-order linear recurrences with variable coefficients, systems of three or more recurrences, divide and conquer with several terms (T(n/2) and T(n/3)) and nonlinear recurrences these substitutions don't make linear.