# Thread: solving a nonhomogenous recursion

1. ## solving a nonhomogenous recursion

Hello ,would you please solve the following non homogenous recursion:

[{a[n+1]-a[n]
=2n+3,a[0]=1},a,n]

2. Hello,
Originally Posted by seamoh
Hello ,would you please solve the following non homogenous recursion:

[{a[n+1]-a[n]
=2n+3,a[0]=1},a,n]
Note that $\displaystyle a_n=a_n-a_{n-1}+a_{n-1}-a_{n-2}+\dots+a_1-a_0+a_0=a_0+\sum_{k=0}^{n-1} 2k+3=1+2\sum_{k=0}^{n-1} k+3\sum_{k=0}^{n-1} 1$

Then use this formula : $\displaystyle \sum_{k=0}^n k=\frac{n(n+1)}{2}$ and you're done.

Spoiler:
$\displaystyle 1+2\sum_{k=0}^{n-1} k+3\sum_{k=0}^{n-1}=1+2\cdot\frac{n(n-1)}{2}+3n=1+n(n-1)+3n=(n+1)^2$

and we get the same result as Soroban

3. Hello, seamoh!

Solve the following non-homogenous recursion:

. . $\displaystyle a(n+1)-a(n) \:=\: 2n+3\qquad a(0) \:=\:1$
We have: .$\displaystyle a(n+1) \;=\;a(n) + 2n+3$

$\displaystyle \begin{array}{cccccccccc} \text{Let }n = 0\!: & a(1) &=& a(0) + 2(0)+3 &=& 1 + 0 + 3 & \Longrightarrow & a(1) \:=\:4 \\ \text{Let }n=1\!: & a(2) &=& a(1) + 2(1) + 3 &=& 4 + 2 + 3 & \Longrightarrow & a(2) \:=\:9 \\ \text{Let }n = 2\!: & a(3) &=& a(2) + 2(2) + 3 &=& 9 + 4 + 3 & \Longrightarrow & a(3) \:=\:16\end{array}$

The sequences seems to be squares.
. . I would conjecture that: .$\displaystyle a(n) \:=\:(n+1)^2$

$\displaystyle \begin{array}{cccccc} \text{We have:} & a(n+1) &=& a(n) + 2n+3 & [1]\\ \text{Next term: } & a(n+2) &=& a(n+1) + 2(n+1)+3 & [2] \end{array}$

Subtract [1] from [2]: .$\displaystyle a(n+2) - a(n+1) \;=\;a(n+1) - a(n) + 2$

$\displaystyle \begin{array}{cccccc} \text{We have:} & a(n+2) &=& 2a(n+1) - a(n) + 2 & [3] \\ \text{Next term:} & a(n+3) &=&2a(n+2) - a(n+1) + 2 & [4] \end{array}$

Subtract [3] from [4]: .$\displaystyle a(n+3) - a(n+2) \;=\;2a(n+2) - 2a(n+1) - a(n+1) + a(n)$

We have: .$\displaystyle a(n+3) - 3a(n+2) + 3a(n+1) - a(n) \;=\;0$

Let $\displaystyle a(n) \:=\:X^n\!:\;\;X^{n+3} - 3X^{n+2} + 3X^{n+1} - X^n \;=\;0$

Divide by $\displaystyle X^{n}\!:\;\;X^3 - 3X^2 + 3X + 1 \:=\:0 \quad\Rightarrow\quad (X-1)^3 \:=\:0$

We have a triple root: .$\displaystyle X \:=\:1,1,1$

The function has the form: .$\displaystyle a(n) \:=\:A(1^n) + Bn(1^n) + Cn^2(1^n)$
. . That is: .$\displaystyle a(n) \;=\;A + Bn + Cn^2$

We know the first three terms:

. . $\displaystyle \begin{array}{ccccccc} a(0) = 1\!: & A + B(0) + C(0^2) &=& 1 & \Rightarrow & A \;=\;1 \\ a(1) = 4\!: & A + B(1) + C(1^2) &=& 4 & \Rightarrow & A+B+C \:=\:4 \\ a(2) = 9\!: & A + B(2) + C(2^2) &=& 9 & \Rightarrow & A + 2B + 4C \:=\:9 \end{array}$

Solve the system: .$\displaystyle A = 1,\;B = 2,\;C = 1$ . . . Hence: .$\displaystyle a(n) \:=\:1 + 2n + n^2$

. . Therefore: .$\displaystyle a(n) \;=\;(n+1)^2$

4. Hello, seamoh!

Solve the following non-homogenous recursion:

. . $\displaystyle a(n+1)-a(n) \:=\: 2n+3\qquad a(0) \:=\:1$
We have: .$\displaystyle a(n+1) \;=\;a(n) + 2n+3$

$\displaystyle \begin{array}{cccccccccc} \text{Let }n = 0\!: & a(1) &=& a(0) + 2(0)+3 &=& 1 + 0 + 3 & \Longrightarrow & a(1) \:=\:4 \\ \text{Let }n=1\!: & a(2) &=& a(1) + 2(1) + 3 &=& 4 + 2 + 3 & \Longrightarrow & a(2) \:=\:9 \\ \text{Let }n = 2\!: & a(3) &=& a(2) + 2(2) + 3 &=& 9 + 4 + 3 & \Longrightarrow & a(3) \:=\:16\end{array}$

The sequences seems to be squares.
. . I would conjecture that: .$\displaystyle a(n) \:=\n+1)^2$

$\displaystyle \begin{array}{cccccc} \text{We have:} & a(n+1) &=& a(n) + 2n+3 & [1]\\ \text{Next term: } & a(n+2) &=& a(n+1) + 2(n+1)+3 & [2] \end{array}$

Subtract [1] from [2]: .$\displaystyle a(n+2) - a(n+1) \;=\;a(n+1) - a(n) + 2$

$\displaystyle \begin{array}{cccccc} \text{We have:} & a(n+2) &=& 2a(n+1) - a(n) + 2 & [3] \\ \text{Next term:} & a(n+3) &=&2a(n+2) - a(n+1) + 2 & [4] \end{array}$

Subtract [3] from [4]: .$\displaystyle a(n+3) - a(n+2) \;=\;2a(n+2) - 2a(n+1) - a(n+1) + a(n)$

We have: .$\displaystyle a(n+3) - 3a(n+2) + 3a(n+1) - a(n) \;=\;0$

Let $\displaystyle a(n) \:=\:X^n\!:\;\;X^{n+3} - 3X^{n+2} + 3X^{n+1} - X^n \;=\;0$

Divide by $\displaystyle X^{n}\!:\;\;X^3 - 3X^2 + 3X + 1 \:=\:0 \quad\Rightarrow\quad (X-1)^3 \:=\:0$

We have a triple root: .$\displaystyle X \:=\:1,1,1$

The function has the form: .$\displaystyle a(n) \:=\:A(1^n) + Bn(1^n) + Cn^2(1^n)$
. . That is: .$\displaystyle a(n) \;=\;A + Bn + Cn^2$

We know the first three terms:

. . $\displaystyle \begin{array}{ccccccc} a(0) = 1\!: & A + B(0) + C(0^2) &=& 1 & \Rightarrow & A \;=\;1 \\ a(1) = 4\!: & A + B(1) + C(1^2) &=& 4 & \Rightarrow & A+B+C \:=\:4 \\ a(2) = 9\!: & A + B(2) + C(2^2) &=& 9 & \Rightarrow & A + 2B + 4C \:=\:9 \end{array}$

Solve the system: .$\displaystyle A = 1,\;B = 2,\;C = 1$ . . . Hence: .$\displaystyle a(n) \:=\:1 + 2n + n^2$

. . Therefore: .$\displaystyle a(n) \;=\;(n+1)^2$