Recurrence Relation solution

Question

How do I solve the following recurrence relation and what kind is it ? $ a_n = a_{n-1} + c $ ?

where c is constant

Can this relation be considered non-homogenous as $ F(n) = c.n^0 $ ?

Answer 1

This is indeed a non-homogeneous relation, the simplest you can think of.

Starting from

$$a_1=a_0+c,$$ you have $$a_2=a_1+c=a_0+2c,\\ a_3=a_2+c=a_0+3c\\ a_4=a_3+c=a_0+4c\\\cdots$$

Do I need to continue ?

---

The standard way to solve a linear recurrence is by

• solving the homogeneous equation

$$a_n=a_{n-1},$$ i.e. by recurrence $$a_n=a_0.$$

• finding a particular solution of the non-homogeneous equation $$a_n=a_{n-1}+c.$$ As this is a first order equation and the RHS is constant, we will try a linear form $$a_n=rn+s.$$ Plugging in the equation $$r(n+1)+s=rn+s+c,$$i.e. $$r=c,$$and $s$ undeterminate. To ensure that $a_0=a_0$, we take $s=0$, and

$$a_n=a_0+cn.$$

Answer 2

You can first calculate the first terms of this sequence.

$$\begin{array}{rclclcl} a_1&=&a_0+c &&&&\\ a_2&=&a_1+c &=& a_0+c+c &=& a_0+2c \\ a_3&=&a_2+c&=& a_0+2c+c &=& a_0+3c \\ a_4&=&a_3+c&=& a_0+3c+c &=& a_0+4c \\ \end{array}$$

Do you see a pattern? Can you prove it?