This solution does not satisfy the recurrence equation. Indeed, according to this solution, Substituting this into the equation, we get , while it should be .I know the answer is

To solve the equation, follow these steps.

1. Note that when is fixed, the sequence is uniquely determined. Therefore, everything further will use some fixed parameter .

2. Write , , , and explicitly (using ). Hint: don't compute and don't add the powers of 2; for example, leave instead of 12 or .

3. Guess the regularity and write the general formula for . You may use the formula , so .

4. Prove by induction that this is indeed the solution. Namely, verify that is given by this formula, and that for every , if is given by the formula, then so is .