# What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$ [closed]

Problem:

Find the closed-form expression for$$T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1 \tag{1}$$where $$T_1 = 1 .$$

Calculating this sum I came up with the following result: $$T_n = 8^{\left(n-1\right)} \tag{2} \,,$$ but is this result correct?

I know the sequence is:\begin{align} T_1 & = 1 \\ T_2 & = 8 \\ T_3 & = 64 \\ & ~~\vdots \end{align}

Questions:

1. What would be the closed-form of $$T_n ?$$

2. What would be the best way to find it?

• Closed-Form, sorry – Horvy May 21 '19 at 1:42
• It looks like you had answered the last two questions before you raised them. – John L. May 21 '19 at 3:25
• Have you tried proving your conjecture by induction? – Yuval Filmus May 21 '19 at 4:03
• This question is more suitable for Mathematics. – Yuval Filmus May 21 '19 at 16:40

After calculating a few values, you can guess the solution and then easily prove it by induction. Another way to find it is to use "creative cancellation": $$1 + 7 (T_1 + \cdots + T_{n-1}) = T_n = (T_n + \cdots + T_1) - (T_{n-1} + \cdots + T_1).$$ Hence if you put $$S_n = T_1 + \cdots + T_{n-1}$$, you deduce $$S_n = 8S_{n-1} + 1.$$ In order to make this homogeneous, take $$R_n = S_n + c$$: $$R_n = S_n + c = 8S_{n-1} + 1 + c = 8(R_{n-1} - c) + 1 + c = 8R_{n-1} + 1 - 7c.$$ Choosing $$c = 1/7$$, this gives $$R_n = 8R_{n-1}$$, and so $$R_n = 8^{n-1} R_1$$. Now $$R_1 = S_1 + 1/7 = T_1 + 1/7 = 8/7$$, and so $$R_n = 8^n/7$$.
It follows that $$S_n = (8^n-1)/7$$ and $$T_n = S_n - S_{n-1} = (8^n - 8^{n-1})/7 = 8^{n-1}$$.
Let me conclude by giving a combinatorial interpretation for the recurrence. I will show that $$T_n$$ is the number of base-8 numbers of length $$n-1$$. Indeed, any such number is either 0, or starts with a non-zero digit followed by a number $$i < n-1$$ digits long.