[Math] Find an explicit formula for the recursive sequence

discrete mathematicsinductionrecurrence-relationsrecursionsequences-and-series

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.

Best Answer

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$

Related Question