# Find an explicit formula for the recursive sequence

Problem: A sequence is defined recursively as follows:

$$S_0 = 1, ~S_k = 2^k - S_k - 1 ~\forall k \in \mathbb{N}_{\geq 1}$$

Use iteration to guess the explicit formula for the sequence. Use mathematical induction to verify that the sequence matches the explicit formula you guessed.

My attempt:

$$S_0 = 1,~S_1 = 1,~S_2 = 3,~S_3 = 5,~S_4 = 11$$

From here, I saw that the answer to $S_1$ could be substituted into $S_2$ and so on..

This gave me the equation $$S_k = 2^k - 2^{k - 1} + (k - 1)$$

When trying to prove this via induction, I stuck here:

Sj+1 = 2j+1 - (2j + 2j-1) + (j - 1)

At this point, I don't really know what to do or how to end up with Sj+1. Is my explicit formula wrong? Is there something else I should be looking for?

Another thing I have trouble with on these problems is finding the pattern for each explicit formula. Every single problem I've had seems to get the formula with a different pattern each time, doing something I wouldn't have guessed in a million years. Is there a good strategy to find a pattern for these formulas, or are there any tips to recognize these patterns?

Thanks.

Hint:

• Your formula is not correct.
• The first few elements are: $1, 1, 3, 5, 11, 21, 43, 85, 171, 341$.
• Write them in binary (i.e. base two), can you see a pattern?

I hope this helps $\ddot\smile$

Use Generating functions.

First, define $s(z) = \sum_{k \ge 0} S_k z^k$, then we have $$S_{k + 1} = 2 \cdot 2^k - S_k$$ Multiply the recurrence by $z^k$, sum over $k \ge 0$ and recognise the sums: $$\frac{s(z) - S_0}{z} = 2 \frac{1}{1 - 2 z} - s(z)$$ As partial fractions: \begin{align} s(z) &= \frac{1}{3} \cdot \frac{1}{1 + z} + \frac{2}{3} \cdot \frac{1}{1 - 2 z} \\ &= \frac{1}{3} \sum_{k \ge 0} (-1)^k z^k + \frac{2}{3} \sum_{k \ge 0} 2^k z^k \end{align} Thus we obtain $$S_k = \frac{2^{k + 1} + (-1)^k}{3}$$

• Sorry to ask, but I'm a bit lost at the second step. I sort of understand what a recurrence might be, but what is the recurrence in this case and how did you multiply it by z^n and then sum over n >= 0 to get (s(z) - S0) / z?
– Alex
May 2, 2014 at 3:51
• @Alex, the function $s(z)$ bundles up all the values of $S_n$ in one easy to manipulate package. This step is to set up an equation for $s$. And I mixed up the indices. Fixing... Thanks! May 2, 2014 at 9:03