1

I've been doing a recurrence relation exercise in my book. Doing some steps and comparing them to the ones taken by the book.

$$T(0) = 1$$

$$T(1) = 2$$

$$T(k) - 7T(k-1)+10T(k-2)=6+8k$$

Characteristic equation:

$$a^2-7a+10$$

$$(a - 5)(a-2)$$

Homogeneous solution:

$$b_0\cdot(5)^n+b_1\cdot(2)^n$$

Wait. My book did something different. Its homogeneous solution is

$$b_0\cdot(2)^n+b_1\cdot(5)^n$$

As you can observe, the book multiplied the constants by the factors in a different order as I did.

My question, then: does it matter? If yes, what determines the order?

Saturn
  • 7,191
  • Addition is commutative, order doesn't matter. – achille hui Apr 10 '14 at 05:42
  • @achillehui: But suppose that $b_0 = 1$ and $b_1 = 2$ and $n = 1$. Clearly $$1\cdot2+2\cdot 5 \neq 2\cdot2+ 1 \cdot 5$$ I'm asking about product distribution, not addition. – Saturn Apr 10 '14 at 05:43
  • 1
    $b_0, b_1$ are parameters you choose to name them. When you flip the role of $2$ and $5$, you need to rename $b_0$ as $b_1$ and $b_1$ as $b_0$. – achille hui Apr 10 '14 at 05:55
  • Let's use different letters, to avoid confusion: your solution is $c_0 5^n + c_1 2^n$. The book's solution is $d_0 2^n + d_1 5^n$. These two sets of solutions are the same, as you can see by putting $c_0 = d_1$ and $c_1 = d_0$. – ShreevatsaR Apr 11 '14 at 05:00

1 Answers1

0

The order doesn't matter.

A general way of solving recurrences like this is as follows. Define the generating function $G(z) = \sum_{n \ge 0} T(n) z^n$, rewrite the recurrence so there aren't subtractions in indices: $$ T(n + 2) - 7 T(n + 1) + 10 T(n) = 8 n + 22 $$ Multiply the recurrence by $z^n$, sum over $n \ge 0$, and recognize: \begin{align} \sum_{n \ge 0} T(n + 1) z^n &= \frac{G(z) - T(0)}{z} \\ \sum_{n \ge 0} T(n + 2) z^n &= \frac{G(z) - T(0) - T(1) z}{z^2} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \end{align} to get: $$ \frac{G(z) - z - 2 z}{z^2} - 7 \frac{G(z) - 1}{z} + 10 G(z) = 8 \frac{z}{(1 - z)^2} + 22 \frac{1}{1 - z} $$ Solve fo $G(z)$, express the result as partial fractions (this is the part where the factorization of the characteristic equation comes up): \begin{align} G(z) &= \frac{1 - 7 z + 33 z^2 - 19 z^3}{1 - 9 z + 25 z^2 - 27 z^3 + 10 z^4} \\ &= \frac{1 - 7 z + 33 z^2 - 19 z^3}{(1 - 5 z) (1 - 2 z) (1 - z)^2} \\ &= \frac{2}{1 - 5 z} - \frac{9}{1 - 2 z} + \frac{6}{1 - z} + \frac{2}{(1 - z)^2} \end{align} Now you can read off the coefficients, if you remember the generalized binomial theorem: $$ (1 - u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} (-u)^k = \sum_{k \ge 0} \binom{m + k - 1}{m - 1} u^k $$ In this case: \begin{align} T(n) &= 2 \cdot 5^n - 9 \cdot 2^n + 6 + 2 (n + 1) \\ &= 2 \cdot 5^n - 9 \cdot 2^n + 2 n + 8 \end{align}

vonbrand
  • 27,812