# What is the general term of this recursive term?

The sequence is defined recursively. Find its general term. $$t_1 = 3, t_n = 2(t_{n-1}) + 3n$$

All I did was find the first couple of terms which are $$3, 12, 33, 78, \dots$$

The only thing common is that all are multiples of 3 but the sequence is neither arithmetic nor geometric. I've no idea how to solve a mixed sequence. Please help.

• See if this answer to a similar question helps. – Brian M. Scott May 19 '20 at 22:54
• Do you know how to solve $t_n=4t_{n-1}-5t_{n-2}+2t_{n-3}$? – J. W. Tanner May 19 '20 at 23:39

Subtract $$t_{n-1}=2t_{n-2}+3n-3$$ from $$t_n=2t_{n-1}+3n,$$ yielding $$t_n-t_{n-1}=2t_{n-1}-2t_{n-2}+3$$;

subtract $$t_{n-1}-t_{n-2}=2t_{n-2}-2t{n-3}+3,$$

yielding the homogenous recurrence $$t_n-2t_{n-1}+t_{n-2}=2t_{n-1}-4t_{n-2}+2t_{n-3}$$

or $$t_n=4t_{n-1}-5t_{n-2}+2t_{n-3}.$$

The characteristic equation is $$x^3-4x^2+5x-2=(x-1)^2(x-2)$$,

so the solution is $$t_n=A2^n+Bn+C$$,

with $$2A+B+C=3$$, $$4A+2B+C=12$$, and $$8A+3B+C=33$$;

i.e., $$A=6, B=-3$$, and $$C=-6$$; i.e., $$t_n=6\times2^n-3n-6.$$

Let's just try it a bit to recognize a pattern: $$t_n=2t_{n-1}+3n=2(2t_{n-2}+3(n-1))+3n$$ $$=4t_{n-2}+(2+1)3n-3\cdot2$$ $$=4(2t_{n-3}+3(n-2))+(2+1)3n-3\cdot2=8t_{n-3}+(4+2+1)3n-3\cdot2-3\cdot4\cdot2$$ $$=8(2t_{n-4}+3(n-3))+(4+2+1)3n-3\cdot2-3\cdot4\cdot2$$ $$=16t_{n-4}+(8+4+2+1)3n-3\cdot2-3\cdot4\cdot2-3\cdot8\cdot3$$ So it looks like this: let $$k be a positive integer, we have $$t_n=2^kt_{n-k}+(2^{k}-1)3n-3\sum_{i=1}^{k-1}\left(2^i\cdot i \right)$$ and let $$S=\sum_{i=1}^{k-1}\left(2^i\cdot i \right)=2\cdot1+4\cdot2+8\cdot3+\dots+2^{k-1}\cdot(k-1)$$ $$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2S=4\cdot1+8\cdot2+\dots+2^{k-1}(k-2)+2^k(k-1)$$ $$\implies S-2S=2+4+8+\dots+2^{k-1}-2^k(k-1)=2^k-2-2^k(k-1)$$ $$\iff S=2^k(k-2)+2$$ and it is easy to prove by induction that $$t_n=2^kt_{n-k}+(2^{k}-1)3n-3(2^k(k-2)+2)$$ for all integers $$k$$ where $$0.

Now substitute $$k=n-1$$ to get $$t_n=2^{n-1}t_1+(2^{n-1}-1)3n-3(2^{n-1}(n-3)+1)-3$$ $$t_1=3 \implies t_n=3(2^{n + 1}-(n+2))$$

• you must have made a mistake; your final formula for $t_n$ does not produce $3,12,33,78,...$ – J. W. Tanner May 20 '20 at 2:20
• @J.W.Tanner I edited the formula right but I am trying to find the mistake, just give me some time – Anas A. Ibrahim May 20 '20 at 2:27
• @J.W.Tanner I got where the mistake was and edited it, now the solution is undoubtedly complete except for the induction part. – Anas A. Ibrahim May 20 '20 at 2:34
• now your answer agrees with mine ;-) – J. W. Tanner May 20 '20 at 2:40