I am trying to turn a summation into a formula, and thought of Newton’s Binomial Theorem but I don't think it would be helpful in this case. I am trying to evaluate possible strings of {1, 2, 3}, and trying to evaluate number of strings that contains odd number of {3} in string of length n. Any suggestion to help practice/turn this summation into a formula? $$\sum_{k=0}^{\lfloor n/2 \rfloor}{\binom{n}{2k+1} \cdot\ \mathrm{2}^{n-(2k +1)}}$$
Thank you
Based on your notations, suppose that there are $P_n$ ways when the string length is $n$, to get $P_{n+1}$, this is what you can do:
Let $s_n$ be a string. Suppose there are even number of 3, you can get an odd sequence by appending a 3 after $s_n$. There are $3^n - P_n$ ways to do so.
Suppose there are odd number of 3, you can get an odd sequence by appending a 1 or a 2. There are $2P_n$ ways to do so. Therefore $P_{n+1} = P_n + 3^n$. Since $P_1 = 1$, you have
$$ P_n = 1 + 3 + \cdots + 3^{n-1} = \frac{3^n - 1}{2}. $$
Alternative solution: $$ \begin{aligned} (2+1)^n &= \sum_{2 \ | \ k}\binom nk 2^{n-k} + \sum_{2 \ | \ (k+1)}\binom nk 2^{n-k}\\ (2-1)^ n &= \sum_{2 \ | \ k}\binom nk 2^{n-k} - \sum_{2 \ | \ (k+1)}\binom nk 2^{n-k}\\ \end{aligned} $$
And then subtract the two formulas and divide by 2.