finding explicit formula through substitution method The question ask us to guess an explicit formula for the sequence
$$t_k = t_{k-1} + 3k + 1 ,$$ for all integers $k$ greater than or equal to 1 and 
$t_0 = 0$
Can someone help me with this? Because I am not really familiar with substitution method.
Thanks in advance.
 A: Hint
Another solution : define $y_k=t_k-t_{k-1}=3k+1$. Adding all terms together, since they telescope,
 $$y_k=t_k-t_0=\sum_{i=1}^{k}(3i+1)=3\sum_{i=1}^{k}i+\sum_{i=1}^{k}1=???$$
I am sure that you can take from here.
A: HINT:
Let $t_k=u_k+Ak^2+Bk+C,$
$u_k+Ak^2+Bk+C=u_{k-1}+A(k-1)^2+B(k-1)+C+3k+1 $
$\iff u_k+2Ak+B-A=u_{k-1}+3k+1 $
Set $B-A=1,2A=3$ so that $u_k=u_{k-1}\implies u_k=u_1=u_0$
As $\implies t_0=0, 0=u_0+C\iff u_0=-C\implies t_k=Ak^2+Bk$ for integer $k\ge0$
Now find $A,B$
A: Hint: use the generating function. At the beginning it looks cumbersome, but gives you a powerful general approach to solving such problems. 
For a starter, $\sum_{k=0}^{\infty} z^k = \frac{1}{1-z}$ and $\sum_{k=1}^{\infty}k z^k = \frac{z}{(1-z)^2}$ for $|z|<1$. Now, define a generating function $G(z) = \sum_{k=0}^{\infty}a_k z^k$. Now, rewrite you expression as
$$
a_{k+1} = a_k + 3 k + 4
$$ 
Now the main step: multiply both sides by $z^k$ and sum over $k$:
$$
\sum_{k=0}^{\infty}a_{k+1} z^k  = \sum_{k=0}^{\infty}a_k z^k  +3 \sum_{k=0}^{\infty} k z^k + 4 \sum_{k=0}^{\infty}z^k = G(z) + \frac{3z}{(1-z)^2} + \frac{4}{1-z}
$$
The first term on the RHS is exactly a generating function, the remaining terms can be written as above. The term on LHS needs a bot of algebra - do it and get $\frac{G(z) - a_0}{z} = \frac{G(z)}{z}$. Now you get 
$$
G(z) = z G(z) + \frac{3 z^2}{(1-z)^2} + \frac{4z}{1-z}\\
G(z) = \frac{3 z^2}{(1-z)^3} + \frac{4z}{(1-z)^2}
$$
You're almost there! To expand the terms on the RHS you need to apply the very same identities we started with. You should get:
$$
G(z) = \sum_{k=0}^{\infty}\frac{3k(k-1)}{2}z^k + \sum_{k=0}^{\infty}4k z^k = \sum_{k=0}^{\infty}\bigg( 3 \binom{k}{2} + 4 \binom{k}{1}\bigg)z^k
$$
Now all you have to do is set $k=n$ and equate coefficients on the LHS and RHS to get the closed-form expression:
$$
a_n = 3 \binom{n}{2} + 4 \binom{n}{1}
$$
A: $$t_k = t_{k-1} + 3k + 1 ,$$ for all integers $k$ greater than or equal to 1 and 
$t_0 = 0$
$$t_{k-1} = t_{k-2} + 3(k-1) + 1 ,$$
$$t_{k-2} = t_{k-3} + 3(k-2) + 1 ,$$
$$t_{k-3} = t_{k-4} + 3(k-3) + 1 ,$$
$$t_k = t_{k-1} + 3k + 1 ,$$
$$t_k = t_{k-2} + 3(k-1) + 1 + 3k + 1 $$
$$    = t_{k-2} + 3[(k-1)+k] + 1(2)$$
$$t_k = t_{k-3} + 3(k-2) + 1 + 3[(k-1)+k] + 1(2)$$
$$    = t_{k-3} + 3[(k-2)(k-1)+k] + 1(3)$$
$$  t_{k-k} + 3[(k(k+1))/2] + 1(k)$$
$$ = 0 + 3[(k(k+1))/2] + 1(k)$$
$$ = 3[(k(k+1))/2] + (k)$$
