# Calculating the sequence sum

Calculate the sum of n elements of the sequence $a_n$, in which: $a_1=3$, $a_2=33$, $a_3=333$, $a_4=3333$ and so forth.

We see that it's not an arithmetic progression as 3333-333 is not equal to 333-33 and so on. It also isn't geometric progression as 3333/333 is not equal to 333/33 and so on.

Though, we see the corelation of: $a_2=10*a_1+3$, $a_3=10*a_2+3$ and so on. Then, the sum is: $10^0*3+(10^1*3+3)+(10^2*3+10^1*3+3)+...+(10^{n-1}*3+10^{n-2}*3+...+10^0*3)$ - but is there any way to shorten it? I can't see any.

-

The sequence $(a_k)$ is a close relative of a geometric progression. Note that $$3a_k=10^k-1.$$

Thus $$3\sum_{k=1}^n a_k=\sum_{k=1}^n 10^k -\sum_{k=1}^n 1=\frac{10^{n+1}-10}{9}-n.$$

-
Um.. but let n=3 and it doesn't hold. $\frac{10^4-10}{9}-3=110-3=107$, which is not true at all. Edit: Whoops, sorry! You're right :) Thank you very much. –  Bringiton Oct 16 '11 at 17:48

As you have noticed $a_{k+1} = 10 a_k + 3$. Let $b_n = \sum_{k=1}^n a_k$, then $$\begin{eqnarray} \sum_{k=1}^n a_{k+1} &=& 10 \sum_{k=1}^n +3 n \\ b_{n+1} - a_1 &=& 10 b_n + 3n \\ b_{n+1} &=& 10 b_n + 3(n+1) \end{eqnarray}$$ Solving this latter equation is as easy as the original recursion. Being linear, it's equal to the sum of solution of homogeneous equation, which is $b_n^{(0)} = c_1 10^n$ and a particular solution, which is clearly linear in $n$, so $b_n^{(1)} = c_2 n + c_3$. Plugging $b_n^{(1)}$ into equation we find $c_2 = 10 c_2 + 3$, and $c_3 + c_2 = 10 c_3 + 3$, thus $c_2 = -\frac{1}{3}$, $c_3= -\frac{10}{27}$. Since $b_1 = 3$, we find

$$b_n = \frac{10}{27} 10^{n} - \frac{9n + 10}{27} = \frac{10}{27} \left( 10^n-1 \right) - \frac{n}{3}$$

Verification:

-
Thank you very much :) –  Bringiton Oct 16 '11 at 18:05