Equation of a curve whose difference in ordinate values form an arithmetic sequence

Question

I have the following recurrence equation that I have obtained while trying to solve a problem:-

$$T(0) = 1$$ $$T(n) = T(n-1) + 9n - 8: n \ge 1$$

The values of $T(n)$ for $n = 0,1,2,... $ are as follows:

n     T(n)
_____________
0     1
1     2
2     12
3     31
4     59
5     96
6     142
7     197
8     261

I want to find a equation for $T(n)$ in closed form. It is clear to me that the difference in the values of consecutive $T(n)$ is in arithmetic sequence with a common difference of $9$, i.e.,

$1, 10, 19, 28...$

Is there a general method to find the equation for such relations?

Answer 1

The recurrence equation has the form $$ \begin{align} T(n) &=c(n) + T(n-1) = c(n) + c(n-1) + T(n-2) = \ldots \\ &= c(n) + c(n-1) + \cdots + c(1) + T(0) \\ &= 1 +\sum_{k=1}^n c_k \end{align} $$ Since $c_n = 9 n - 8$ the expression for $T(n)$ is $$ T(n) = 1 + \sum_{k=1}^n (9 k - 8) = 1 + 9 \sum_{k=1}^n k - 8 n = 1 + 9 \frac{n+1}{2} n - 8n = \frac{9n-7}{2} n + 1 $$ The sum can also be directly evaluated as the sum of elements of arithmetic progression sequence, i.e. (first element + last element)/2 times number of elements: $$ 1 + \frac{9\cdot n-8 + (9 \cdot 1 - 8)}{2} n = 1 + \frac{9n -8 + 1}{2} n = 1 + \frac{9n-7}{2} n $$ Checking against your table:

In[50]:= Table[1/2 (2 - 7 n + 9 n^2), {n, 0, 8}]

Out[50]= {1, 2, 12, 31, 59, 96, 142, 197, 261}

Answer 2

You might consider doing the following computations and it will be clear how to construct a closed form: $$T(1)=T(0)+(9-8)$$ $$T(2)=T(0)+(9-8)+(9*2-8)$$ $$T(3)=T(0)+(9-8)+(9*2-8)+(9*3-8)$$ $$...$$ I'm sure you can "rearrange" the expressions I gave here to see the general closed form; continue a few terms if necessary.

The general approach to see the pattern in these types of recurrences is to express each $T(n)$ in terms of $T(0).$ This will yield an expression that depends only on $T(0)$ and $n$. Thus, you'll have the closed form as long as you know $T(0)$. And here we do know, so you are set.