Is this Strong Induction approach?

Question

Let f(n) denote the number of ternary strings(0, 1, 2) with no two consecutive nonzero digits. For example, 0102 is valid but 0120 and 1102 are not. Use Strong Induction to show that for all $$n \geq 1$$

$$f(n) = \frac{4 \cdot 2^n-(-1)^n}{3}$$

Start by finding a recursive formula. What are your bases cases, how many do you need?

My solution (Is this strong induction?; How can I solve this with strong induction? Any hint or solution?).

For base cases, (I counted 0, 1, 00, 11,.. so on) $$f(1) = 5; f(2) = 8;$$

$$f(n+1) = \frac{4 \cdot 2^{n+1}-(-1)^{n+1}}{3}$$ $$= \frac{4 \cdot 2 \cdot 2^n -(-1)(-1)^n}{3}$$ $$= \frac{4 \cdot (3-1) \cdot 2^n -(-1)(-1)^n}{3}$$ $$= \frac{12 \cdot 2^n - 4 \cdot 2^n + (-1)^n}{3}$$ $$= 4 \cdot 2^n - f(n)$$

f(n+1) is true. QED.

Answer 1

You say you found the recursion $f_n=f_{n-1}+2f_{n-2}$, given the story. Your solution of the problem then should include (i) a proof of this recursion, (ii) a proof that the suggested $f$ satisfies this recursion, and (iii) a proof that the suggested $f$ gives the correct values for $n=1$ and $n=2$.

Answer 2

OK, let's take a shot at this.

Call $f_n$ the number of sequences of length $n$ that satisfy your conditions. It is clear there is just one of length 0, three of length 1.

Consider a sequence like you want of length $n$. If the last digit is zero, before that one you have $f_{n - 1}$ possible sequences; if the last digit is non-zero, the one before is zero and before that there is one of the $f_{n - 2}$ sequences of length $n - 2$. There are $2$ possible ends (01, 02). Thus:

$\begin{equation*} f_n = f_{n - 1} + 2 f_{n - 2} \end{equation*}$

To solve this one, use generating functions. Define $F(z) = \sum_{n \ge 0} f_n z^n$, shift by two, multiply by $z^n$, sum over $n \ge 0$ and recognize resulting sums:

$\begin{align*} \sum_{n \ge 0} f_{n + 2} z^n &= \sum_{n \ge 0} f_{n + 1} z^n + 2 \sum_{n \ge 0} f_n z^n \\ \frac{F(z) - f_0 - f_1 z}{z^2} &= \frac{F(z) - f_0}{z} + 2 F(z) \end{align*}$

As partial fractions:

$\begin{align*} F(z) &= \frac{4}{3 (1 - 2 z)} - \frac{1}{3 (1 + z)} \\ [z^n] F(z) &= \frac{4}{3} \cdot 2^n - \frac{(-1)^n}{3} \\ &= \frac{2^{n + 2} - (-1)^n}{3} \end{align*}$

If you absolutely insist on induction, for base you see that the formula gives the correct values $f_0 = 1$ and $f_1 = 3$. If you assume it works up to $n$, you get:

$\begin{align*} f_{n + 1} &= f_n + 2 f_{n - 1} \\ &= \frac{2^{n + 2} - (-1)^n}{3} + 2 \cdot \frac{2^{n + 1} - (-1)^{n - 1}}{3} \\ &= \frac{2^{n + 2} - (-1)^n + 2 \cdot 2^{n + 1} - 2 \cdot (-1)^{n - 1}}{3} \\ &= \frac{2^{n + 3} - (-1)^{n + 1}}{3} \end{align*}$

This is what the formula says.