Question

Solve the recurrence relation xn = xn−1 + 2n + 1 where x0 = 1​

Answer 1

We need to solve the recurrence relation,

$\longrightarrow x_n=x_{n-1}+2n+1$

Replacing $n$ by $k,$

$\longrightarrow x_k=x_{k-1}+2k+1$

$\longrightarrow x_k-x_{k-1}=2k+1$

Taking summation in the limit from $k=1$ to $n,$

$\displaystyle\longrightarrow\sum_{k=1}^n\left(x_k-x_{k-1}\right)=\sum_{k=1}^n(2k+1)$

$\displaystyle\longrightarrow\sum_{k=1}^nx_k-\sum_{k=1}^n x_{k-1}=2\sum_{k=1}^nk+\sum_{k=1}^n1$

We know that,

• $\displaystyle\sum_{k=1}^nk=\dfrac{n(n+1)}{2}$

• $\displaystyle\sum_{k=1}^n1=n$

Then,

$\displaystyle\longrightarrow\sum_{k=1}^nx_k-\sum_{k=1}^n x_{k-1}=2\cdot\dfrac{n(n+1)}{2}+n$

$\displaystyle\longrightarrow\sum_{k=1}^nx_k-\sum_{k=1}^n x_{k-1}=n^2+2n$

But we see that,

• $\displaystyle\sum_{k=1}^nx_{k-1}=\sum_{k=0}^{n-1}x_k$

Then,

$\displaystyle\longrightarrow\sum_{k=1}^nx_k-\sum_{k=0}^{n-1} x_k=n^2+2n$

Take,

• $\displaystyle\sum_{k=1}^nx_k=\sum_{k=1}^{n-1}x_k+x_n$

• $\displaystyle\sum_{k=0}^{n-1}x_k=x_0+\sum_{k=1}^{n-1}x_k$

Then,

$\displaystyle\longrightarrow\left(\sum_{k=1}^{n-1}x_k+x_n\right)-\left(x_0+\sum_{k=1}^{n-1}x_k\right)=n^2+2n$

$\displaystyle\longrightarrow\sum_{k=1}^{n-1}x_k+x_n-x_0-\sum_{k=1}^{n-1}x_k=n^2+2n$

$\displaystyle\longrightarrow x_n-x_0=n^2+2n$

$\displaystyle\longrightarrow x_n=n^2+2n+x_0$

Given that $x_0=1.$

$\displaystyle\longrightarrow x_n=n^2+2n+ 1$

$\displaystyle\longrightarrow\underline{\underline{x_n=(n+1)^2}}$

This is the general form of our recurrence relation.

Answer 2

$\huge{\underline{\underline{\mathrm{\red{AnswEr}}}}}$

We need to solve the recurrence relation,

$\longrightarrow x_n=x_{n-1}+2n+1$

Replacing $n$ by $k,$

$\longrightarrow x_k=x_{k-1}+2k+1$

$\longrightarrow x_k-x_{k-1}=2k+1$

Taking summation in the limit from $k=1$ to $n,$

$\displaystyle\longrightarrow\sum_{k=1}^n\left(x_k-x_{k-1}\right)=\sum_{k=1}^n(2k+1)$

$\displaystyle\longrightarrow\sum_{k=1}^nx_k-\sum_{k=1}^n x_{k-1}=2\sum_{k=1}^nk+\sum_{k=1}^n1$

We know that,

$\displaystyle\sum_{k=1}^nk=\dfrac{n(n+1)}{2}$

$\displaystyle\sum_{k=1}^n1=n$

Then,

$\displaystyle\longrightarrow\sum_{k=1}^nx_k-\sum_{k=1}^n x_{k-1}=2\cdot\dfrac{n(n+1)}{2}+n$

$\displaystyle\longrightarrow\sum_{k=1}^nx_k-\sum_{k=1}^n x_{k-1}=n^2+2n$

But we see that,

$\displaystyle\sum_{k=1}^nx_{k-1}=\sum_{k=0}^{n-1}x_k$

Then,

$\displaystyle\longrightarrow\sum_{k=1}^nx_k-\sum_{k=0}^{n-1} x_k=n^2+2n$

Take,

$\displaystyle\sum_{k=1}^nx_k=\sum_{k=1}^{n-1}x_k+x_n$

$\displaystyle\sum_{k=0}^{n-1}x_k=x_0+\sum_{k=1}^{n-1}x_k$

Then,

$\displaystyle\longrightarrow\left(\sum_{k=1}^{n-1}x_k+x_n\right)-\left(x_0+\sum_{k=1}^{n-1}x_k\right)=n^2+2n$

$\displaystyle\longrightarrow\sum_{k=1}^{n-1}x_k+x_n-x_0-\sum_{k=1}^{n-1}x_k=n^2+2n$

$\displaystyle\longrightarrow x_n-x_0=n^2+2n$

$\displaystyle\longrightarrow x_n=n^2+2n+x_0$

Given that $x_0=1.$

$\displaystyle\longrightarrow x_n=n^2+2n+ 1$

$\displaystyle\longrightarrow\underline{\underline{x_n=(n+1)^2}}$

This is the general form of our recurrence relation.