Very confused by recurrence relations as a concept

Question

We've been introduced to recurrence relations as a concept in my Discrete class. One question asks:

Given the recurrence:

$S(1) = 1$,

$S(n) = 2S(n − 1) + 3 (for \ n > 1)$

prove by induction that for all $n ≥ 1$: $$S(n) = 2^{n+1} − 3$$

This seems to be similar to making proofs via induction. I guess $S(n) = 2^{n+1} − 3$ can be considered the 'closed form' of the recurrence described by $2S(n − 1) + 3$, because it's not recursive?

I've tried replacing the $S(n − 1)$ in $2S(n − 1) + 3$ with $2S(n-2)+3$ to get:

$S(n) = 2(2S(n-2)+3)+3$

Which comes out to : $2^2S(n-2)+9$.

I think I'm supposed to deduce a pattern from all this, which I think is:

$2^k s(n-k) + 3^k$

...Am I on the right track at least? I'm not sure how I'm supposed to relate this back to the base case or prove this is identical to $S(n) = 2^{n+1} − 3$. I'm used to using k to solve things inductively, but for whatever reason I'm not sure how k and n work in proving recurrence relations. It just isn't clicking for me. Any insight or advice would be most welcome.

Answer 1

Obviously the claim is satisfied for $n=1$, as $S(1) = 2^{1+1} - 3 = 1$. Now assume that the claim is true for some $k \in \mathbb{N}$, then we have:

$$S(k+1) = 2S(k) + 3 = 2(2^{k+1} - 3) + 3 = 2^{(k+1) + 1} - 6 + 3 = 2^{(k+1) + 1} - 3$$

Hence the proof.

---

You've already been given the general form of the solutions. But in order to derive it on your own note that $S(k+1) - 2S(k) = 3 = S(k) - 2S(k-1) \implies S(k+1) = 3S(k) - 2S(k-1)$. Hence the characteristic equations of the reccurence relations is: $x^2 - 3x + 2 = 0$, whose solutions are $x=2$ and $x=1$. Hence the general formula for the sequence is of the form $S(n) = a\cdot 2^n + b\cdot 1^n$.

Solving for $S(1)$ and $S(2)$ we have:

$$\begin{cases} 2a + b = 1 \\ 4a + b = 5 \end{cases} \implies \begin{cases} a = 2 \\ b = -3 \end{cases}$$

Hence: $\boxed{S(n) = 2^{n+1} - 3}$

Answer 2

You are on the right track. You're given a recurrence relation and asked to prove its closed form via induction. In your induction proof, when you consider $S(n+1)$, you will need to use the recurrence relation to invoke the $S(n)$ case.

Answer 3

You appear to be doing things the hard way. That is, you seem to be trying to do the exercise

Find a closed form for $S(n)$

and working under the pretense that you don't alrady know what the closed form is. However, the problem you're asked to solve is:

Here is the closed form for $S(n)$. Check that it's correct.

which is a much easier problem.

The easiest way to do this is to check that the closed form satisfies the same recursion; i.e. that if we define $T(n) = 2^{n+1} - 3$, then you just need to verify the equations

• $T(1) = 1$
• $T(n) = 2T(n-1) + 3$ (for all $n > 1$)

An inductive proof is only necessary if you don't yet already know that a recursive formula defines a (unique) function, in which case you basically have to replicate the proof that $S$ and $T$ define the same function.