Find an explicit formula for the recursive sequence

Question

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:

S_j+1 = 2^j+1 - (2^j + 2^j-1) + (j - 1)

At this point, I don't really know what to do or how to end up with S_j+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.

Answer 1

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$

Answer 2

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} $$