Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.
Problem 2
The sum of the first $n$ terms of the sequence
$$ 1, (1 + 2), (1 + 2 + 2^2), …, (1 + 2 + … + 2^{k - 1}), … $$
is of the form $2^{n + R} + Sn^2 + Tn + U$ for all $n > 0$. Find $R$, $S$, $T$ and $U$.
Hints
Open to see a hint, but try solving it yourself first!
You have 4 unknowns $(R, S, T, U)$. What do you need to find them?
Solution
Open to see the solution, but try solving it first, or see the hints above.
The given sequence is already defined for us in the general case in the last element:
$$ 1, (1 + 2), (1 + 2 + 2^2), …, \textbf{$(1 + 2 + … + 2^{k - 1})$}, … $$
The $i^{th}$ term of this sequence can thus be written as follows:
$$ a_i = \sum_{k = 1}^{i} 2^{k-1} $$
Then, the sum of the first $n$ terms in the sequence is:
$$ \sum_{i = 1}^n a_i = \sum_{i = 1}^n \sum_{k = 1}^i 2^{k - 1} $$
However, we don’t actually have to expand or simplify the double-summation. Since we have $4$ unknowns, we can just compute the first $4$ values of $A_n$, set them equal, and solve a system of $4$ equations with $4$ unknowns.
Let $A_n = \displaystyle{\sum_{i=1}^n a_i}$, and let’s compute several of the initial values:
$$ \begin{align*} A_1 & = a_1 & = & \; 1 & = & \; 1 \\ A_2 & = a_1 + a_2 & = & \; 1 + (1+2) & = & \; 4 \\ A_3 & = a_1 + a_2 + a_3 & = & \; 1 + (1+2) + (1+2+4) & = & \; 11 \\ A_4 & = a_1 + a_2 + a_3 + a_4 & = & \; 1 + (1+2) + (1+2+4) + (1+2+4+8) & = & \; 26 \\ \end{align*} $$Additionally, per the given problem statement, we also know that
$$A_n = 2^{n + R} + Sn^2 + Tn + U$$
so let’s set them equal for $n = 1, 2, 3, 4$:
$$ \begin{align*} (n = 1) \quad & A_1 & = & \; 1 & = & \; 2^{1 + R} + S + T + U & \quad \text{(1)} \\ (n = 2) \quad & A_2 & = & \; 4 & = & \; 2^{2 + R} + 4S + 2T + U & \quad \text{(2)} \\ (n = 3) \quad & A_3 & = & \; 11 & = & \; 2^{3 + R} + 9S + 3T + U & \quad \text{(3)} \\ (n = 4) \quad & A_4 & = & \; 26 & = & \; 2^{4 + R} + 16S + 4T + U & \quad \text{(4)} \\ \end{align*} $$We now have $4$ equations and $4$ unknowns.
Reorganizing equation $(1)$ to put $R$ on one side, and all the other variables on the other side, we get:
$$ \begin{align*} & 2^{1 + R} + S + T + U = 1 & \quad \text{from eq. $1$} \\ & 2^{1 + R} = 1 - S - T - U & \quad \text{solve for $2^{1+R}$ $(5)$} \\ \end{align*} $$since $2^{1+R}$ appears in all other equations and $R$ does not as a separate variable, we don’t have to solve for $R$, and can substitute the result in $(5)$ into the remaining equations $(2)$, $(3)$, and $(4)$ to remove the use of variable $R$, leaving us with $3$ equations and $3$ unknowns $(S, T, U)$.
Let’s now take equation $(2)$, separate out $2^{1+R}$ and substitute the result from $(5)$:
$$ \begin{align*} 2 \cdot 2^{1 + R} + 4S + 2T + U & = 4 & \quad \text{from eq. 2} \\ 2 \cdot (1 - S - T - U) + 4S + 2T + U & = 4 & \quad \text{substitute from eq. 5} \\ 2 - 2S - 2T - 2U + 4S + 2T + U & = 4 & \quad \text{expand} \\ 2 + 2S - U & = 4 & \quad \text{simplify} \\ 2S - 2 & = U & \quad \text{solve for $U$ (6)} \\ \end{align*} $$Now let’s take equation $(3)$ and similarly substitute from both $(5)$ and $(6)$:
$$ \begin{align*} 2^2 \cdot 2^{1 + R} + 9S + 3T + U & = 11 & \quad \text{from eq. 3} \\ 2^2 \cdot (1 - S - T - U) + 9S + 3T + U & = 11 & \quad \text{substitute $2^{1+R}$ from eq. 5} \\ 4 - 4S - 4T - 4U + 9S + 3T + U & = 11 & \quad \text{expand} \\ 5S - T - 3U & = 7 & \quad \text{simplify} \\ 5S - T - 3(2S - 2) & = 7 & \quad \text{substitute $U$ from eq. 6} \\ 5S - T - 6S + 6 & = 7 & \quad \text{expand} \\ -S - T & = 1 & \quad \text{simplify} \\ -S - 1 & = T & \quad \text{solve for $T$ (7)} \\ \end{align*} $$Finally, let’s take equation $(4)$ and substitute the results from $(5)$, $(6)$, and $(7)$ to eliminate all other variables and solve for $S$:
$$ \begin{align*} 2^3 \cdot 2^{1 + R} + 16S + 4T + U & = 26 & \quad \text{from eq. 4} \\ 2^3 \cdot (1 - S - T - U) + 16S + 4T + U & = 26 & \quad \text{substitute $2^{1+R}$ from eq. 5} \\ 8 - 8S - 8T - 8U + 16S + 4T + U & = 26 & \quad \text{expand} \\ 8 + 8S - 4T - 7U & = 26 & \quad \text{simplify} \\ 8 + 8S - 4(-S - 1) - 7U & = 26 & \quad \text{substitute $T$ from eq. 7} \\ 8 + 8S - 4(-S - 1) - 7(2S -2) & = 26 & \quad \text{substitute $U$ from eq. 6} \\ 8 + 8S + 4S + 4 - 14S + 14 & = 26 & \quad \text{expand} \\ (8S + 4S - 14S) + (8 + 4 + 14) & = 26 & \quad \text{combine like terms} \\ -2S + 26 & = 26 & \quad \text{simplify} \\ -2S & = 0 & \quad \text{simplify} \\ S & = 0 & \quad \text{solve for $S$ (8)} \\ \end{align*} $$Now that we have $S = 0$, we can go back and substitute this into earlier equations to find the other unknowns. Let’s start with eq. $(7)$ and compute $T$:
$$ T = -S - 1 = 0 - 1 = -1 $$
Similarly, using eq. $(6)$, we can compute $U$:
$$ U = 2S - 2 = 0 - 2 = - 2 $$
and finally, to compute $R$, we can use eq. $(5)$:
$$ 2^{1 + R} = 1 - S - T - U = 1 - 0 - (-1) - (-2) = 4 = 2^2 $$
Since $2^{1 + R} = 2^2$, we know that $R = 1$. Hence, here are all the unknown values:
$$ \boxed{R = 1; \quad S = 0; \quad T = -1; \quad U = -2} \qquad \blacksquare $$
Verification
Verification of the solution; also gives away the answer!
Now that we’ve solved for $R$, $S$, $T$, and $U$, let’s verify some of the $A_n$ values to make sure it works out:
$$ \begin{align*} A_1 & = \boxed{ 1} & = & \; 2^{1 + R} + S + T + U & = & \; 2^{1 + 1} + 0 - 1 - 2 & = & \; 4 - 3 & = & \; \boxed{ 1} \\ A_2 & = \boxed{ 4} & = & \; 2^{2 + R} + 4S + 2T + U & = & \; 2^{2 + 1} + 0 - 2 - 2 & = & \; 8 - 4 & = & \; \boxed{ 4} \\ A_3 & = \boxed{11} & = & \; 2^{3 + R} + 9S + 3T + U & = & \; 2^{3 + 1} + 0 - 3 - 2 & = & \; 16 - 5 & = & \; \boxed{11} \\ A_4 & = \boxed{26} & = & \; 2^{4 + R} + 16S + 4T + U & = & \; 2^{4 + 1} + 0 - 4 - 2 & = & \; 32 - 6 & = & \; \boxed{26} \\ \end{align*} $$Checks out!