Now count the number of such numbers that do **not** contain two consecutive 3s. Let $a_n$ be the number of valid sequences of length $n$ with no two consecutive 3s, where each digit is 3 or 4.

["Counting Valid Numbers Without Two Consecutive 3s: A Dynamic Programming Approach", "When we explore sequences made up only of the digits 3 and 4, a fascinating combinatorial problem arises: how many such sequences of length $ n $ avoid having two consecutive 3s?", "Let $ a_n $ represent the number of valid sequences of length $ n $ using digits 3 and 4, where no two 3s appear consecutively. We aim to find a recurrence or closed-form expression for $ a_n $, enabling efficient computation for any $ n $.", "---", "### Understanding the Problem", "Each position in the sequence is either a 3 or a 4. However, a sequence is invalid if it contains "33" anywhere. For example:", "- $ 34 $ — valid\n- $ 343 $ — valid\n- $ 33 $ — invalid\n- $ 344 $ — valid\n- $ 334 $ — invalid", "We need to count only the sequences where $ 33 $ never occurs.", "---", "### Building a Recurrence Relation", "To model this, define $ a_n $ as the total number of valid sequences of length $ n $. We break $ a_n $ based on what the last digit is:", "1. Case 1: The last digit is 4\n The first $ n-1 $ digits form any valid sequence of length $ n-1 $.\n Number of such sequences: $ a_{n-1} $", "2. Case 2: The last digit is 3\n Then the digit before it must not be 3, i.e., must be 4 (or the sequence has length 1).\n So the $ (n-1)^\ ext{th} $ digit must be 4, and the first $ n-2 $ digits form any valid sequence of length $ n-2 $.\n Number of such sequences: $ a_{n-2} $", "Therefore, the recurrence is:\n$$\na_n = a_{n-1} + a_{n-2}\n$$", "---", "### Initial Conditions", "- For $ n = 1 $: Possible sequences: "3", "4" → both valid → $ a_1 = 2 $\n- For $ n = 2 $: Possible sequences:\n - "34", "43", "44" — valid\n - "33" — invalid\n → $ a_2 = 3 $", "These match Fibonacci-like growth.", "---", "### Relating to Fibonacci Numbers", "This recurrence $ a_n = a_{n-1} + a_{n-2} $ with $ a_1 = 2 $, $ a_2 = 3 $ is a shifted Fibonacci sequence.", "Recall the Fibonacci sequence $ F_n $ defined by:\n$ F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2} $", "We observe:\n- $ a_1 = 2 = F_3 $\n- $ a_2 = 3 = F_4 $\n- $ a_3 = a_2 + a_1 = 3 + 2 = 5 = F_5 $\n- $ a_4 = 5 + 3 = 8 = F_6 $\nSo by induction,\n$$\na_n = F_{n+2}\n$$", "Thus, the number of valid sequences of length $ n $ with no two consecutive 3s is exactly the $ (n+2)^\ ext{th} $ Fibonacci number.", "---", "### Interpretation and Usage", "This sequence grows roughly exponentially, since Fibonacci numbers grow as:\n$$\nF_n \sim \frac{\phi^n}{\sqrt{5}}, \quad \phi = \frac{1+\sqrt{5}}{2}\n$$", "So $ a_n = F_{n+2} \approx \frac{\phi^{n+2}}{\sqrt{5}} $", "This recurrence allows efficient computation via dynamic programming:\n- Initialize $ a_1 = 2 $, $ a_2 = 3 $\n- Compute iteratively up to $ n $", "---", "### Example Computations", "| $ n $ | $ a_n $ (valid sequences) | $ F_{n+2} $ |\n|--------|----------------------------|---------------|\n| 1 | 2 | $ F_3 = 2 $ |\n| 2 | 3 | $ F_4 = 3 $ |\n| 3 | 5 | $ F_5 = 5 $ |\n| 4 | 8 | $ F_6 = 8 $ |\n| 5 | 13 | $ F_7 = 13 $|", "---", "### Why This Matters", "This problem models constraints in binary sequences — useful in computer science, coding theory, and combinatorics. The structure taught here — using recurrence to count sequences avoiding a pattern — applies broadly to strings, graphs, and dynamic programming.", "---", "### Final Answer", "The number of valid sequences of length $ n $ using digits 3 and 4 with no two consecutive 3s satisfies the recurrence:\n$$\na_n = a_{n-1} + a_{n-2}, \quad a_1 = 2, \quad a_2 = 3\n$$\nand is given by\n$$\na_n = F_{n+2}\n$$\nwhere $ F_k $ is the $ k^\ ext{th} $ Fibonacci number.", "This elegant solution combines simplicity, recurrence logic, and deep combinatorial insight.", "---", "Keywords: Fibonacci sequence, valid digit sequences, no two consecutive 3s, dynamic programming, count valid strings, recurrence relation, combinatorics, number of sequences avoiding pattern."]