Find sum of series where $U_k = 3 U_{k-1}+1$.

Question

A sequence $(U_n)$ is defined by $U_1 = 2$ and $U_k = 3 U_{k-1} +1.$ Find the sum $U_1+ U_2+ \dots + U_n$

I tried solving using method of undetermined coefficient but this series is not becoming constant.

Answer 1

The method of undetermined coefficients would have worked for you if you had chosen the right form to work with. From $U_k = 3 U_{k-1} +1$ it clearly that $U_k$ is growing like $3^k,$ but it's not a geometric series because of the $+1$. If you guess $$U_k = a\cdot3^k+b$$ the method of undetermined coefficients will give you the correct answer, as you can easily check.

After that, computing the sum is straightforward.

Answer 2

Hint. By setting $$ V_k=U_k+\frac12 $$ one may get a mere geometric sequence $$ V_k=3V_{k-1} $$ then one may just note that $$ U_1+U_2+\cdots+U_n=V_1+V_2+\cdots+V_n-\frac{n}2. $$

Answer 3

Hint: It's not too hard to find a closed form for $U_k$. Consider the first few terms in the sequence:

$$U_2=3U_1+1\\ U_3=3(3U_1+1)+1\\ U_4=3(3(3U_1+1)+1)+1$$

We can see they have the general form of multiplying each bracket by $3$ and then adding $1$. And, in total, there are $(k-1)$ $3$'s and $+1$'s. Hence: $$U_k=\underbrace{3(3(\ldots(3}_{k-1}U_1+\underbrace{1)+\ldots+1)+1}_{k-1}$$

When expanding this, the $U_1$ term is multiplied by all $(k-1)$ $3's$. Then the leftmost $+1$ is multiplied by $(k-2)$ $3$'s. The next is multiplied by $(k-3)$, and so on. Hence:

$$U_k=3^{k-1}U_1+3^{k-2}+3^{k-3}+\ldots+1\\ =3^{k-1}U_1+\sum_{r=0}^{k-2}3^r$$

You can simplify this further and easily sum the $U_k$.

Answer 4

Let $V_n=U_1+U_2+\dots+U_{n}$. Then $$ V_{n+1}-V_n=U_{n+1} $$ and $$ V_{n+2}-V_{n+1}=U_{n+2}=3U_{n+1}+1=3(V_{n+1}-V_n)+1 $$ whence $$ V_{n+2}-4V_{n+1}+3V_n=1 $$ OK, there's still a constant term; however $$ V_{n+3}-4V_{n+2}+3V_{n+1}=V_{n+2}-4V_{n+1}+3V_n $$ and so $$ V_{n+3}-5V_{n+2}+7V_{n+1}-3V_n=0 $$ The characteristic equation is $X^3-5X^2+7X-3=0$, whose roots are $3$ (single) and $1$ (double), so the general solution is $$ V_n=a\cdot1^n+bn\cdot 1^n+c3^n $$ Since $V_1=2$, $V_2=9$, $V_3=31$, you can easily compute $a$, $b$ and $c$.