Recursive Sequences Proofs
Back to Recursive Sequences
Common properties
Proofs:
- The number of words of length n in alphabet {1,2,...,d} avoiding words "11", "22", ..., "kk" is the recurrence sequence with initial terms a(0) = 1, a(1) = d and the recurrence relation a(n) = (d-1)a(n-1) + (d-k)a(n-2).
Proof: Let the words described above be divided into two parts: ending in {1,2,...,k} and ending in {k+1,...,d}. Let b(n) be the number of words of length n ending in {1,2,...,k} and c(n) be the number of words of length n ending in {k+1,...,d}. Obviously, a(n) = b(n) + c(n). We can get any word of length n ending in {k+1,...,d} by taking any word of length n-1 and adding one of the letters {k+1,...,d}. Thus c(n) = (d-k)a(n-1). We can get any word of length n ending in {1,2,...,k} by taking any word of length n-1 and adding any one of the letters {1,2,...,k} except we should subtract the words that we get that are ending in {11,22,...,kk}. Hence b(n) = k*a(n-1) - b(n-1). Putting the counts together we get a(n) = (d-1)a(n-1) + c(n-1) = (d-1)a(n-1) + (d-k)a(n-2). Initial conditions are trivially checked.
- Let p and q be the roots of the equation x2 - dx - k = 0. Then the sequence a(n) = pn + qn satisfies the recurrence a(n) = da(n-1) + ka(n-2) with the initial conditions a(0) = 2, a(1) = d.
Proof: pn + qn = (p+q)(pn-1 + qn-1) - pq(pn-2 + qn-2).
- Let p and q be the roots of the equation x2 - dx - k = 0. Then the sequence a(n) = (pn - qn)/(p-q) satisfies the recurrence a(n) = da(n-1) + ka(n-2) with the initial conditions a(0) = 0, a(1) = 1.
Proof: pn - qn = (p+q)(pn-1 - qn-1) - pq(pn-2 - qn-2).
a(n) = d * a(n-1) - a(n-2)
Proofs:
- The number of 01-avoiding words of length n on alphabet {0,1,2, ..., d-1} that do not end in 0 is
equal to a(n), where a(n) = d * a(n-1) - a(n-2) and a(0) = 1, a(1) = d-1.
Proof: It is easy to see that you can get a word that ends in 1 from any valid word of length n-1.
That is, the number of words of length n that end in 1 is a(n-1). Similarly, suppose that a word ends in b ≥ 1, which has
exactly k zeroes before the last digit b. The number of such words is a(n-k-1). Hence, the total number of words
ending in b is a(n-1) + a(n-2) + ... + a(1) + a(0). Summing up, the result is
a(n) = (d-1) * a(n-1) + (d-2) * (a(n-2) + a(n-3) + ... + a(1) + a(0)). The equivalent of this to the initial recursion is
proved in the corresponding bullet below.
- The number of domino tilings of Sd-1 × P2n (product of a star graph and a path graph) is equal to a(n), where a(n) = d * a(n-1) - a(n-2) and a(0) = 1, a(1) = d-1. Also the number of domino tilings in Sd-1 × P2n+1 (product of a star graph and a path graph) with d-3 non-central vertices removed from the last star is equal to a(n), where a(n) = d * a(n-1) - a(n-2) and a(0) = 1, a(1) = d.
Proof:
Let us first prove the first statement. Let us start with noticing that if we want to tile a star graph with dominoes we can only place one domino and it must include the center of the star. Let us associate the center of the star graph with 0 and associate other vertices with numbers from 2 to d-1. Let us associate the domino tilings of Sd-1 × P2 with a number. If all dominoes are parallel to the path P2, then we associate this tiling with one. Otherwise exactly two dominoes are not parallel to P2 and they connect the center of the star with the vertex number k (k ≥ 2) and we associate this tiling with k. Now we would like to correspond to a number a domino tiling of Sd-1 × P2m which cannot be decomposed into two smaller domino tilings of that type. It is easy to see that in this tiling there are only two dominoes that are not parallel to P2m: one domino in the first star and one domino in the last star. They both have to connect the center of the star with the same numbered vertex. Suppose this number is k. Then we associate this tiling with the word "000...000k", where we have m-1 zeroes. If the tiling can be decomposed into the minimal ones, then we concatenate all the words corresponding to minimal tilings together. This way we create a correspondence between domino tilings of Sd-1 × P2n and the number of 01-avoiding words of length n on alphabet {0,1,2, ..., d-1} that do not end in 0.
The second statement can be proved in a similar manner as the first statement.
- If a(n) = d * a(n-1) - a(n-2), then a(n+1)a(n-1) - a(n)2 is a constant. For the
sequence that starts as a(0) = 1 and a(1) = d-1, this constant is equal to d-2. For the
sequence that starts as a(0) = 1 and a(1) = d, this constant is equal to -1.
Proof:
By applying the recursion equation for a(n+2) to the difference of expressions a(n+1)a(n-1) - a(n)2 and the same expression with n replaced by n-1 we get:
a(n+2)a(n) - a(n+1)2 - a(n+1)a(n-1) + a(n)2
= da(n+1)a(n) - a(n)2 - a(n+1)2 - a(n+1)a(n-1) + a(n)2 = a(n+1) (da(n) - a(n+1) - a(n-1)) = 0. Hence, a(n+2)a(n) - a(n+1) doesn't depend on n and is equal to a(0)a(2) -
a(1)2.
- If a(n) = d * a(n-1) - a(n-2), then a(n+2)a(n-1) - a(n)a(n+1) is a constant. For the
sequence that starts as a(0) = 1 and a(1) = d-1, this constant is equal to d(d-2). For the
sequence that starts as a(0) = 1 and a(1) = d, this constant is equal to -d.
Proof: By applying the recursion equation to a(n+2) and expressing a(n-1) through a(n+1) and a(n) we get:
a(n+2)a(n-1) - a(n)a(n+1) = (d * a(n+1) - a(n)) (d * a(n) - a(n+1)) - a(n)a(n+1) = d2 * a(n+1)a(n) -
d * a(n+1)2 - d * a(n)2 = d * (a(n+1)(d * a(n) - a(n+1)) - a(n)2) =
d * (a(n+1)a(n-1) - a(n)2). The expression a(n+1)a(n-1) - a(n)2 is a constant by another
property. Hence a(n+2)a(n-1) - a(n)a(n+1) is constant. For the initial conditions a(0) = 1 and a(1) = d-1 this constant is equal to d(d-2).
For the initial conditions a(0) = 1 and a(1) = d this constant is equal to -d.
- If a(n) = d * a(n-1) - a(n-2) with initial terms a(0) = 1, a(1) = d-1, then a(n) = (d-1) * a(n-1) + (d-2) * (a(n-2) + a(n-3) + ... + a(1) + a(0)).
Proof: Let us prove this by induction. The first step is trivial as a(1) = (d-1) * a(0). Assume that we proved that a(n-1) = (d-1) * a(n-2) + (d-2) * (a(n-3) + a(n-4) + ... + a(1) + a(0)). Adding this to the recurrence relation a(n) = d * a(n-1) - a(n-2) we get a(n) = (d-1) * a(n-1) + (d-2) * (a(n-2) + a(n-3) + ... + a(1) + a(0)).
- The number of 01-avoiding words of length n on alphabet {0,1,2, ..., d-1} is
equal to a(n), where a(n) = d * a(n-1) - a(n-2) and a(0) = 1, a(1) = d.
Proof: Let us denote b(n) (correspondingly c(n)) as the number of words in this sequence of length n
that end (correspondingly do not end) in 0. Hence a(n) = b(n) + c(n). It is easy to see that b(n) = a(n-1), as we
can get a valid word ending in 0 by attaching 0 to any valid word. We can get a word not ending in 0 by attaching any
digit other than 0 and 1 to any valid word, or by attaching 1 to any valid word not ending in 0. Hence c(n) = (d-2)*a(n-1) + c(n-1). Now we can replace c(n-1) as a(n-1) - b(n-1), which gives us c(n) = (d-1)*a(n-1) - b(n-1) = (d-1) * a(n-1) - a(n-2). Summing b and c we get a(n) = d*a(n-1) - a(n-2).
- Let p and q be the roots of the equation x2 - dx + 1 = 0. Then the sequence a(n) = pn + qn satisfies the recurrence a(n) = da(n-1) - a(n-2) with the initial conditions a(0) = 2, a(1) = d.
Proof: Set k equal to -1 in the general proof.
- Let p and q be the roots of the equation x2 - dx + 1 = 0. Then the sequence a(n) = pn + qn approaches Round(pn).
Proof: As p*q equals 1, then pn tends to 0.
a(n) = d * a(n-1) + d * a(n-2)
Proofs:
- Let p and q be the roots of the equation x2 - dx - d = 0. Then the sequence a(n) = pn + qn satisfies the recurrence a(n) = da(n-1) + da(n-2) with the initial conditions a(0) = 2, a(1) = d.
Proof: Set k equal to d in the general proof.
- a(n) with initial terms a(0) = 1 and a(1) = d+1 and the recurrence relation a(n) = da(n-1) + da(n-2) equals the number of 00-avoiding words of length n on alphabet {0,1,2, ..., d}.
Proof: Set k equal to 1 in the general proof above and adjust it slightly.
a(n) = d * a(n-1) + a(n-2)
Proofs:
- a(n) with initial terms a(0) = 1 and a(1) = d+1 and the recurrence relation a(n) = da(n-1) + a(n-2) equals the number of words in the alphabet {0, 1, 2, ..., d} avoiding "11", "22", ..., "dd".
Proof: The proof is similar to the general proof.
- Let p and q be the roots of the equation x2 - dx - 1 = 0. Then the sequence a(n) = pn + qn satisfies the recurrence a(n) = da(n-1) + a(n-2) with the initial conditions a(0) = 2, a(1) = d.
Proof: Set k equal to 1 in the general proof.
- Let d = 2k, then the sequence a(n) with the recurrence relation a(n) = 2ka(n-1) + a(n-2) and the initial terms a(1) = k, a(2) = 2k2+1 are numerators of continued fraction converging to the square root of k2+1. The sequence of denominators follows the same recurrence with the initial condition correspondingly a(1) = 1, and a(2) = 2k. (For example, the first two continued fraction approximations are: k and (2k2+1)/2k.
Proof: Let x be the square root of k2+1; then x = k + 1/z, where 1/z is less than 1. It is easy to see that z = x+k, meaning that z = 2k + 1/z. Hence the continued fractions for z is [2k; 2k, 2k, 2k, ...].
Let c(n) and d(n) be the numerators and denominators of continued fractions converging to z. We can see that c(n)/d(n) = 1 + 1/(c(n-1)/d(n-1)). Hence c(n) = 2kc(n-1) + d(n-1) and d(n) = c(n-1). Hence the numerators and denominators of continued fractions converging to z form the same sequence (shifted by one index relative each other) with the recurrence relation a(n) = da(n-1) + a(n-2) and the initial terms a(0) = 1 and a(1) = 2k. Denominators for x are the same as for z and numerators for x are linear combinations of numerators and denominators for z (namely c(n) - kd(n)). The rest of the proof follows from an easy calculation.
Last revised December 2007