2
$\begingroup$

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?

$\endgroup$

closed as off-topic by xskxzr, Evil, Yuval Filmus, Juho, David Richerby May 25 at 13:21

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about computer science, within the scope defined in the help center." – xskxzr, Evil, Yuval Filmus, Juho
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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.

$\endgroup$
  • $\begingroup$ Thanks for the trouble! $\endgroup$ – Horvy May 21 at 23:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.