What is the number of n-digit numbers that can be written with the numbers 2, 3 and 4 that add up to be odd?

Question

What is the number of 4-digit numbers that can be written with the numbers 2, 3 and 4 that add up to be odd?

for example: 3-23-32-43-34-223-243-232-234-322-324-342-344-... ... n-digit numbers.

Answer 1

Let $a_n$ be the number of $n$-digit numbers with digits from $\{2,3,4\}$ with an odd number of $3$s. Consider two mutually exclusive cases:

1. If the first $n-1$ digits contain an odd number of $3$s, the $n$th digit must be $2$ or $4$.
2. If the first $n-1$ digits contain an even number of $3$s, the $n$th digit must be $3$.

These two cases imply that $$a_n = 2a_{n-1} + (3^{n-1}-a_{n-1}) = a_{n-1} + 3^{n-1}.$$ The initial condition is $a_0=0$, and iterating the recurrence yields $$a_n = \sum_{k=0}^{n-1} 3^k = \frac{3^n-1}{3-1} = \frac{3^n-1}{2}.$$