solve the non homogeneous recurrence relation These recurrences should be simple to solve but I see a ton of different ways to do it, such as general solution, particular solution etc. We did not talk about these in class, just need to get the general form of it. If anyone could help and explain (simple) would be great. Thank you!
$a_{n} = a_{n-1} + 2n + 1 ,   a_{0}=1, a_{1}=4$
 A: And here is a completely different way of doing it - I'll leave you to work out for yourself what it means ;-)

$$\matrix{\bullet\cr}\qquad
  \matrix{\bullet&\circ\cr \circ&\circ\cr}\qquad
  \matrix{\bullet&\circ&\bullet\cr \circ&\circ&\bullet\cr
    \bullet&\bullet&\bullet\cr}\qquad
  \matrix{\bullet&\circ&\bullet&\circ\cr \circ&\circ&\bullet&\circ\cr
    \bullet&\bullet&\bullet&\circ\cr
    \circ&\circ&\circ&\circ\cr}\qquad
  \matrix{\bullet&\circ&\bullet&\circ&\bullet\cr \circ&\circ&\bullet&\circ&\bullet\cr
    \bullet&\bullet&\bullet&\circ&\bullet\cr
    \circ&\circ&\circ&\circ&\bullet\cr \bullet&\bullet&\bullet&\bullet&\bullet\cr}$$

A: There are many references around to the general method, but here is a nice short cut for this particular example.  We have
$$a_n-a_{n-1}=2n+1\ .$$
Since $n$ is a variable we can replace it by $n-1$, $n-2$, and so on until we get to $1$.  This gives
$$\eqalign{
  a_n-a_{n-1}&=2(n)+1\cr
  a_{n-1}-a_{n-2}&=2(n-1)+1\cr
  a_{n-2}-a_{n-3}&=2(n-2)+1\cr
  \vdots\cr
  a_2-a_1&=2(2)+1\cr
  a_1-a_0&=2(1)+1\ .\cr}$$
Now add up all these equations and look carefully at what you get on the left hand side.
By the way, you don't need to specify the value of $a_1$ since you can calculate it once $a_0$ is given.
A: A related problem. Another way to go is

$$ a_{n+1}-a_n=2n+1 \implies \sum_{i=0}^{n-1}(a_{i+1}-a_i)=\sum_{i=0}^{n-1}(2i+1)=\dots\,. $$

Other techniques.
Note: You need the following identity

$$ \sum_{i=1}^{n} i = \frac{n(n+1)}{2}. $$

