# Is this Strong Induction approach?

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.

• Why is $f(1)=5$ ? Commented Feb 14, 2018 at 13:23
• Welcome to SE. Sadly, this isn't right. Your algebra starts from what you hope is true and ends up with a statement you don't know is true, because you've shown no reason in the problem that explains where the $4 \cdot 2^n$ comes from. If you can do that then you could write the algebra the other way and you'd be fine. That would be a proof using ordinary induction. Since the problem seems to call for strong induction that's not likely to work. So you really need to start from scratch, trying to find the recursive formula. How could you compute $f(n+1)$ if you knew all earlier values of $f$? Commented Feb 14, 2018 at 13:28
• You haven't defined what $f(n)$ is. You wrote something, but note that you never explained what it has to do with $n$. (And this seems serious, since yoyr value for $f(1)$ makes no sense.) Then you say that $f(n+1)$ is true, which makes no sense either, since $f(n)$ is a number rather than a statement. Then you write endless lines of algebra. Why? You have not used once the definition of $f$. Commented Feb 14, 2018 at 13:37
• should I find all f(1), f(2), to the f(n) to find f(n+1)???? I just understood what the strong induction is, but I'm not sure how I can approach this problem. Commented Feb 14, 2018 at 13:38
• I found f(n) = f(n-1) + 2*f(n-2) using ternary string property. So I should prove this like... since f(n) = f(n-1) + 2*f(n-2) is true by diagram, f(n+1) is true, so it's true by strong induction? Commented Feb 14, 2018 at 13:39

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

• (Plus an explanation of why this proves that $f (n)$ satusfies the suggested formula for all $n$.) Commented Feb 14, 2018 at 20:35
• Can you help me with this proof too? math.stackexchange.com/questions/2658988/… Commented Feb 20, 2018 at 19:32

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.