Recursive Sequences Proofs

Back to Recursive Sequences

• Common properties
• a(n) = d * a(n-1) - a(n-2)
• a(n) = d * a(n-1) + d * a(n-2)
• a(n) = d * a(n-1) + d * a(n-2)

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 x² - dx - k = 0. Then the sequence a(n) = pⁿ + qⁿ satisfies the recurrence a(n) = da(n-1) + ka(n-2) with the initial conditions a(0) = 2, a(1) = d.
  Proof: pⁿ + qⁿ = (p+q)(p^n-1 + q^n-1) - pq(p^n-2 + q^n-2).
• Let p and q be the roots of the equation x² - dx - k = 0. Then the sequence a(n) = (pⁿ - qⁿ)/(p-q) satisfies the recurrence a(n) = da(n-1) + ka(n-2) with the initial conditions a(0) = 0, a(1) = 1.
  Proof: pⁿ - qⁿ = (p+q)(p^n-1 - q^n-1) - pq(p^n-2 - q^n-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 S_d-1 × P_2n (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 S_d-1 × P_2n+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 S_d-1 × P₂ with a number. If all dominoes are parallel to the path P₂, then we associate this tiling with one. Otherwise exactly two dominoes are not parallel to P₂ 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 S_d-1 × P_2m 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 P_2m: 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 S_d-1 × P_2n 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)² 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)² and the same expression with n replaced by n-1 we get: a(n+2)a(n) - a(n+1)² - a(n+1)a(n-1) + a(n)² = da(n+1)a(n) - a(n)² - a(n+1)² - a(n+1)a(n-1) + a(n)² = 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)².
• 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) = d² * a(n+1)a(n) - d * a(n+1)² - d * a(n)² = d * (a(n+1)(d * a(n) - a(n+1)) - a(n)²) = d * (a(n+1)a(n-1) - a(n)²). The expression a(n+1)a(n-1) - a(n)² 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 x² - dx + 1 = 0. Then the sequence a(n) = pⁿ + qⁿ 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 x² - dx + 1 = 0. Then the sequence a(n) = pⁿ + qⁿ approaches Round(pⁿ).
  Proof: As p*q equals 1, then pⁿ tends to 0.

a(n) = d * a(n-1) + d * a(n-2)

Proofs:

• Let p and q be the roots of the equation x² - dx - d = 0. Then the sequence a(n) = pⁿ + qⁿ 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 x² - dx - 1 = 0. Then the sequence a(n) = pⁿ + qⁿ 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) = 2k²+1 are numerators of continued fraction converging to the square root of k²+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 (2k²+1)/2k.
  Proof: Let x be the square root of k²+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.

• Back to Tanya Khovanova's welcome page

• Contact me: Tanya Khovanova

  tanyakh@yahoo.com

Last revised December 2007