finding explicit formula through substitution method

Question

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.

Answer 1

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$

Answer 2

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.

Answer 3

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} $$

Answer 4

$$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)$$