0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ In your proof by induction, what do you think the induction hypothesis should be? $\endgroup$ – littleO Jun 21 '16 at 21:07
  • $\begingroup$ Did your course already prove the existence and uniqueness theorem for solutions of such recurrences? If so, you need only verify that $\,2^{n+1}-3\,$ satisfies the recurrence hence, by uniqueness, it equals $\,S(n)\,$ (note $S$ exists by the existence part). $\endgroup$ – Bill Dubuque Jun 21 '16 at 23:22
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thank you for this. Is it usually okay to plug in the closed form of a recurrence relation in making a proof like this like you did for S(k+1)? That's not considered begging the question at all? $\endgroup$ – Chris T Jun 21 '16 at 21:37
  • $\begingroup$ @ChrisT Pretty much yes, as long as we use the math induction. On the other hand solely the fact that $S(k) = 2^{k+1} - 3 \implies S(k+1) = 2^{k+2} - 3$ for some $k \in \mathbb{N}$ means nothing to us. Can you check that this rule isn't violated for some $k$? Not possible, as there are infinitely many natural numbers. Therefore we use induction and so we use the base step, inductive hypothesis and inductive step. $\endgroup$ – Stefan4024 Jun 21 '16 at 21:41
  • $\begingroup$ @ChrisT From you views on the problem it seems like your biggest problem is understanding the concept of induction. You shouldn't backtrack like you did, instead you should start from somewhere and go forward step by step. I mean think of an infinite line of dominos. We know that "somebody" has pushed the first domino (Base Case) and as long as the $k-th$ dominot falls then the $(k+1)-th$ will fall too, which are the Inductive Hypothesis and Inductive Step parts of the proof. $\endgroup$ – Stefan4024 Jun 21 '16 at 21:45
  • $\begingroup$ @ChrisT Proof by induction is very much "begging the question." You assume that the conclusion is true in order to prove that it is true. If P(n) means "our proposition is true in case n." We show that P(1) it true. And, show that P(k+1) is true when P(k) is true. If P(k+1) always follows P(k) and P(1) is true, then P(2) is true because P(1) is true. And P(3) is true because P(2) is true. etc. $\endgroup$ – Doug M Jun 21 '16 at 22:01
  • 1
    $\begingroup$ Doug and Stefan, thank you for clarifying - I've never thought about it that induction that way but it makes sense that we are "begging the question" to prove a more complex version of something $\endgroup$ – Chris T Jun 21 '16 at 22:06
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Looks like I made things too complicated. I think I was overthinking things because my Professor made a special point of saying that if we are trying to prove equation x = equation y, we should not begin with the assumption that equation y is the same as equation x - but I think as Doug and Stefan point out below, that's sort of the whole point of inductive reasoning. $\endgroup$ – Chris T Jun 21 '16 at 22:10
  • $\begingroup$ @ChrisT: You can reconcile it by thinking of each $n$ as giving a different equation, and then inductively computing the truth of each equation in terms of its predecessor. You're never assuming the instance of the equation you're trying to prove; your assumption is always the previous instance(s). $\endgroup$ – user14972 Jun 21 '16 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.