Recurrence Relationship Questions

Question

Consider the recurrence defined by:

$$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$

Determine what Gn is for several values of n to determine a formula for Gn.

1. $2n$
2. $n$
3. $2n-1$
4. $n^2$

*I believe this one is 2n

Answer 1

Just cheat, and use generating functions. Define $G(z) = \sum_{n \ge 0} G_n z^n$. Write the recurrence so there aren't subtractions in indices: $$ G_{n + 1} = G_n + 2 n + 1 $$ Multiply by $z^n$, sum over $n \ge 0$, recognize: \begin{align} \sum_{n \ge 0} G_{n + 1} z^n &= \frac{G(z) - G_0}{z} \\ \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} This gives: $$ \frac{G(z)}{z} = G(z) + 2 \frac{z}{(1 - z)^2} + \frac{1}{1 - z} $$ Solving for $G(z)$: $$ G(z) = \frac{z + z^2}{1 - 3 z + 3 z^2 - z^3} = \frac{1}{1 - z} - 3 \frac{1}{(1 - z)^2} + 2 \frac{1}{(1 - z)^3} $$ Using the generalized binomial theorem: \begin{align} G_n &= \binom{-1}{n} (-1)^n - 3 \binom{-2}{n} (-1)^n + 2 \binom{-3}{n} (-1)^n \\ &= \binom{n + 1 - 1}{1 - 1} - 3 \binom{n + 2 - 1}{2 - 1} + 2 \binom{n + 3 - 1}{3 - 1} \\ &= 1 - 3 \frac{n + 1}{1!} + 2 \frac{(n + 2)(n + 1)}{2!} \\ &= n^2 \end{align}

Answer 2

HINT :

Hopefully this will help you solve the question.

Otherwise you can just calculate the first 3-4 $G_n$ and see to which of the proposed solutions it corresponds : \begin{eqnarray*} G_0 &=& 0\\ G_1 &=& G_0 + 2\cdot1 - 1 \qquad n = 1 \text{ here}\\ &=& 0 + 2 - 1\\ &=& 1\\ G_2 &=& G_1 + 2\cdot2 - 1 \qquad n = 2 \text{ here}\\ &=&... \end{eqnarray*}

Now keep on going.