Solving recurrence relations?

Question

How do I solve $$ a_{n} = a_{n-1} + n, a_{0} = 1$$??

I solved for n=1 thru n=5:

1: 2 = a₀ + 1
2: 4 = a₀ + 1 + 2 = a₀ + 3
3: 7 = a₀ + 3 + 3 = a₀ + 6
4: 11 = a₀ + 6 + 4 = a₀ + 10
5: 16 = a₀ + 10 + 5 = a₀ + 15

I'm failing to see THE pattern. I see that for each iteration from n=1, the number you add to a_0 (=1) increments by one from the last iteration in the sequence... like n=2, it's the a_0 + 1 we started with + 2 makes a_0 + 3, and for n=3, we have a_0 + 6 which is the last one + 3, for n=4 it's +4, etc.... but that's still reliant upon previous iterations, not a direct solution without having to actually iterate through them. How do I extract the solution? Isn't there an actual WAY to go about it?

Answer 1

Hint: Think about triangular numbers.

Follow up: To derive the formula, simply observe that the second differences are constant. This implies a quadratic relationship between $n$ and $a_n$. So what quadratic passes through $(1,1)$, $(2,3)$, and $(3,6)$?

Answer 2

A little intuition about that sequence http://en.wikipedia.org/wiki/Triangular_number

Answer 3

The numbers $1,3,6,10,15$ are the triangular numbers $T_n$. They have formula $\frac 12n(n+1)$. You might know that formula. If not, you can take the first differences, getting $1,2,3,4,5$ and second differences getting $1,1,1,1,1$. The fact that the second line is constant says the polynomial that generates the sequence is of second degree. The fact that the second difference is $1$ says the leading term is $\frac 1{2!}$. You can then subtract off the leading term and find the linear term.

Answer 4

Use telescoping: $a_n = (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + ....+ (a_2 - a_1) + (a_1 - a_0) + a_0 = n + (n-1) + ...+ 2 + 1 + 1 = \dfrac{n(n+1)}{2} + 1$

Answer 5

One clear pattern is that the right-hand side of your equations is always $a_0$ plus some number. The numbers to add to $a_0$ follow the sequence $1, 3, 6, 10, 15, 21, \ldots .$ Now, many sequences can be analyzed by finding out something about the rate at which the terms increase (the percentage increase, not the value added each time). For the Fibonacci sequence, for example, we find that the ratio of terms approaches $\tfrac12(1+\sqrt5)$ (the "golden ratio") as the sequence continues to infinity.

If you look at the rate at which the numbers increase in this sequence, you may notice that the rate is actually slowing down. In fact, $$\frac31 = 3,\ \frac63 = 2,\ \frac{10}{6} = \frac53, \ \frac{15}{10} = \frac32,\ \frac{21}{15} = \frac75,$$ and so forth. You may notice that the ratios steadily decrease; the pattern is a little more obvious if we do not reduce the fractions quite to the lowest terms: $$\frac31 = \frac31,\ \frac63 = \frac42,\ \frac{10}{6} = \frac53, \ \frac{15}{10} = \frac64,\ \frac{21}{15} = \frac75.$$ That is, $$\frac{a_n - a_0}{a_{n-1} - a_0} = \frac{n+1}{n-1}.$$ But the value of $a_n - a_0$ is just the cumulative effect of all these increases: $$\begin{eqnarray} a_n - a_0 &=& (a_1 - a_0) \cdot \frac{a_2 - a_0}{a_1 - a_0} \cdot \frac{a_3 - a_0}{a_2 - a_0} \cdot \frac{a_4 - a_0}{a_2 - a_0} \cdot \cdots \cdot \frac{a_{n-1} - a_0}{a_{n-2} - a_0} \cdot \frac{a_n - a_0}{a_{n-1} - a_0} \\ &=& 1 \cdot \frac31 \cdot \frac42 \cdot \frac53 \cdot \cdots \cdot \frac{n-1}{n-3} \cdot \frac{n}{n-2} \cdot \frac{n+1}{n-1}. \end{eqnarray}$$ Now notice that each numerator from $3$ through $n-1$ inclusive (that is, all but the last two) cancels the denominator of the fraction after the next in this product. That is, all but the first two denominators end up being canceled. We end up with $$ a_n - a_0 = 1 \cdot \frac11 \cdot \frac12 \cdot {n} \cdot (n+1) = \frac{n(n+1)}{2}. $$

That was a very unconventional way of looking at this sequence, but when we come to a new problem that we are completely unfamiliar with, we may try many different things. The way people usually solve a sequence like this (for the first time) is more like the following:

Sometimes it is useful not to combine the numbers too much. So instead of writing $$\begin{eqnarray} a_1 &=& a_0 + 1, \\ a_2 &=& a_0 + 1 + 2 = a_0 + 3, \\ a_3 &=& a_0 + 3 + 3 = a_0 + 6, \\ a_4 &=& a_0 + 6 + 4 = a_0 + 10, \end{eqnarray}$$ and so forth, you could write $$\begin{eqnarray} a_1 &=& a_0 + 1, \\ a_2 &=& a_0 + 1 + 2, \\ a_3 &=& a_0 + 1 + 2 + 3, \\ a_4 &=& a_0 + 1 + 2 + 3 + 4, \end{eqnarray}$$ and so forth. A pattern then emerges: $$ a_n = a_0 + 1 + 2 + 3 + \cdots + n. $$ Now there is a famous story that says a 10-year-old boy named Karl Friedrich Gauss came up with a trick for adding these numbers quickly.

A variation of Gauss's method is to write the sum twice, but reverse the order of the numeric terms on the second writing: $$\begin{eqnarray} a_n &=& a_0 + 1 + 2 + 3 + \cdots + n, \\ a_n &=& a_0 + n + (n - 1) + (n - 2) + \cdots + 1. \end{eqnarray}$$

Now we can add the two values on the left side, and add the two equal values on the right side term by term, and obtain a new equation, $$\begin{eqnarray} 2a_n &=& 2a_0 + (n + 1) + ((n - 1) + 2) + ((n - 2) + 3) + \cdots + (1 + n) \\ &=& 2a_0 + \underbrace{(n+1) + (n+1) + (n+1) + \cdots + (n+1)}_{n} \\ &=& 2a_0 + n(n+1). \end{eqnarray}$$ It is easy to find $a_n$ for any $n$ if you provide the value of $a_0$ in this equation.

Answer 6

$$ a_0 = 1 $$ $$ a_n = a_{n-1}+n $$ This recurrence can be rewritten as $$ a_n= a_0+ \sum_{k=1}^n k= 1+\frac{n(n+1)}{2}= \frac{1}{2}\left(n^2+n+2\right) $$