The initial terms of a sequence are: $c_{0}=2, c_{1}=3$, and subsequent terms for $k=2,3,4, \ldots$ can be calculated using the relation $c_{k}=3 c_{k-1}-2 c_{k-2}$. Write $c_{k}$ as a function of $k$ alone. What is the sum $S_{n}$ of the first $n$ terms of this sequence? Express $S_{n}$ in terms of $S_{n-1}$ and $S_{n-2}$.
I. Solution: With the given formation rule, the first 7 terms of the sequence are:

$2, \quad 3, \quad 5, \quad 17, \quad 33, \quad 65$.

Consider the sequence of differences between consecutive terms, thus the calculable terms of this sequence are:

$$
c_{1}-c_{0}=d_{0}=1, \quad c_{2}-c_{1}=d_{1}=2, \quad d_{2}=4, \quad d_{3}=8, \quad d_{4}=16, \quad d_{5}=32
$$

These form a geometric sequence, the ratio of any two consecutive differences is 2. This is true for any two consecutive differences, indeed

$$
\frac{d_{j}}{d_{j-1}}=\frac{c_{j+1}-c_{j}}{c_{j}-c_{j-1}}=\frac{\left(3 c_{j}-2 c_{j-1}\right)-c_{j}}{c_{j}-c_{j-1}}=\frac{2\left(c_{j}-c_{j-1}\right)}{c_{j}-c_{j-1}}=2
$$

and thus $d_{k}=2^{k}$.

Express $c_{k}$ using the $d_{j}$ terms, from which the desired representation is hoped for

$$
\begin{gathered}
c_{k}=\left(c_{k}-c_{k-1}\right)+c_{k-1}=\left(c_{k}-c_{k-1}\right)+\left(c_{k-1}-c_{k-2}\right)+c_{k-2}=\ldots= \\
=\left(c_{k}-c_{k-1}\right)+\left(c_{k-1}-c_{k-2}\right)+\ldots+\left(c_{2}-c_{1}\right)+\left(c_{1}-c_{0}\right)+c_{0}= \\
=d_{k-1}+d_{k-2}+\ldots+d_{1}+d_{0}+c_{0}
\end{gathered}
$$

Thus, substituting the found expression for $d_{j}$ (and reversing the order of the summands)

$$
c_{k}=2+\left(1+2+2^{2}+\ldots+2^{k-1}\right)=2+\frac{2^{k}-1}{2-1}
$$

or

$$
c_{k}=2^{k}+1
$$

Notice that this expression is valid for $k=0$ and $k=1$ as well.

Now the sum of the first $n$ terms:

$$
\begin{gathered}
S_{n}=c_{0}+c_{1}+\ldots+c_{n-1}=\left(2^{0}+1\right)+(2+1)+\ldots+\left(2^{n-1}+1\right)= \\
=\left(1+2+\ldots+2^{n-1}\right)+n \\
S_{n}=2^{n}-1+n
\end{gathered}
$$

To derive the relationship between $S_{n}, S_{n-1}$, and $S_{n-2}$, from (3) and (2) with $k=n$

$$
\begin{aligned}
2^{n}=c_{n}-1 & =S_{n}-n+1, \quad \text { or } \\
c_{n} & =S_{n}-n+2
\end{aligned}
$$

Accordingly,

$$
\begin{aligned}
& c_{n-1}=S_{n-1}-(n-1)+2 \\
& c_{n-2}=S_{n-2}-(n-2)+2
\end{aligned}
$$

Substituting these into the given relationship

$$
\begin{gathered}
S_{n}-n+2=3\left(S_{n-1}-n+3\right)-2\left(S_{n-2}-n+4\right) \\
S_{n}=3 S_{n-1}-2 S_{n-2}-1
\end{gathered}
$$

Bach Katalin (Szeged, Rózsa F. g. III. o. t.)

Remarks. 1. If we already suspect the $c_{k}=2^{k}+1$ relationship, it can also be proven by induction: it is valid for $k=0$, 1, and if $k-1$ and $k-2$ are numbers for which $c_{k-1}=2^{k-1}+1, c_{k-2}=2^{k-2}+1$, then $k$ is also such, because

$$
c_{k}=3 c_{k-1}-2 c_{k-2}=(2+1)\left(2^{k-1}+1\right)-2\left(2^{k-2}+1\right)=2^{k}+1
$$

Similarly, the (4) relationship can be proven if we have noticed it.

Miklóssy Endre (Szolnok, Verseghy F. g. IV. o. t.)

2. The (4) relationship can also be obtained by the following reasoning. On the right side of (3), the $2^{n}, n$ terms need to be expressed in terms of $S_{n-1}, S_{n-2}$. For this purpose, the equalities obtained from (3) by substituting $n-1$ and $n-2$ for $n$:

$$
n+\frac{2^{n}}{2}=S_{n-1}+2, \quad n+\frac{2^{n}}{4}=S_{n-2}+3
$$

can be written in the form of a system of equations for the "unknowns" $n$ and $2^{n}$:

$$
n=-S_{n-1}+2 S_{n-2}+4, \quad 2^{n}=4 S_{n-1}-4 S_{n-2}-4
$$

and substitute the obtained expressions into $S=n+2^{n}-1$.

3. The (4) relationship surprisingly resembles the sequence formation rule. This can also be proven without the "closed form" calculations of (2) and (3) if we add the equations column-wise:

$$
\begin{array}{rlr}
c_{n-1} & =3 c_{n-2}-2 c_{n-3} \\
c_{n-2} & =3 c_{n-3}-2 c_{n-4} \\
\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\
c_{2} & =3 c_{1}-2 c_{0} \\
c_{1} & =3 c_{0} \quad-3 \\
c_{0} & =r
\end{array}
$$

4. A large portion of the solutions mechanically used $S_{n}$ to denote the sum whose highest indexed term is $c_{n}$, although according to the given text, this symbol should be $S_{n+1}$ - and consequently, they obtained $S_{n}=2^{n+1}+n$ instead of (3). We accepted these, but we note that a careful reader should pay particular attention to "unusual" things - such as the 0-indexed term of the sequence here. Even more numerous are the solutions that do not mention that (3) is valid not only for $k \geq 2$. (Indeed, in the reasoning leading to (2), they used the given relationship, which makes no sense for $k=0$ and 1.)