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.

Skip to content
# The number of n-digit numbers that can be written with the numbers 2, 3 and 4 that add up to be odd?

###### Related Question

combinationscombinatoricscombinatorics-on-wordsexamples-counterexamples

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.

## Best Answer

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:

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