How many finite sequnces $x_1,x_2,x_3,\ldots,x_m$ are there such that $x_i =1$ or $2$ and $\sum_{i=1}^{m}x_i=10$ [closed]

Question

How many finite sequnces $x_1,x_2,x_3,\ldots,x_m$ are there such that $x_i =1$ or $2$ and $\sum_{i=1}^m x_i=10$

A. $89$, B. $91$, C. $92$, D. $120.$

Answer 1

Let $g_n$ be the number of sequences with sum $n$ made up of $1$'s and/or $2$'s. We happen to want $g_{10}$, but it is easier to attack the general problem.

Note that $$g_{n+1}=g_{n}+g_{n-1}.\tag{1}$$ For a sequence with sum $n+1$ is obtained by either appending a $1$ to a sequence with sum $n$, or by appending a $2$ to a sequence of length $n-1$.

Our recurrence is the familiar Fibonacci recurrence, and the $g_n$ are Fibonacci numbers. For note that $g_1=1$ and $g_2=2$. Thus by (1) we have $g_3=3$ and therefore $g_4=5$, and so on. Quickly we find that $g_{10}=89$.

Answer 2

If $\sum x_i = k$ and the $x_i$ are either $1$ or $2$, then we can reduce each variable by $1$ and get $\sum y_i = k - m$ where the $y_i$ are either $0$ or $1$. There are exactly $\binom{k-m}{m}$ solutions to this equation.

So, the total number of solutions is $\displaystyle\sum_{m = 0}^k \binom{k-m}{m}$. This is a famous identity and is equal to the $(k+1)$st Fibonacci number.

For this problem, $F(11) = 89$.

Answer 3

By inspection, we only need to consider the cases where m = 5,6,7,8,9,10.

if m = 5, there is only one option, all 2's.

if m = 10, there is only one option, all 1's.

if m = 6, there are 15 options because we have to have 4 2's and 2 1's. So we have to choose two places to have 1's.

if m = 7, we have to have 3 2's and 4 1's. So we have 35 options, because we have to choose 3 places to have 2's.

if m = 8, we have to have 2 2's so we have 28 options.

if m = 9, we have to have 1 2 so we have 9 options.

Summing them all up we have 1 + 15 + 35 + 28 + 9 + 1 = 89.

Answer 4

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert #1 \right\vert}$

With $m \in {\mathbb N}\,,\ m \geq 1$ and $a > 0$:

\begin{align}&\color{#66f}{\sum_{x_{1}\ =\ 1}^{2}\ldots\sum_{x_{m}\ =\ 1}^{2} \delta_{x_{1} + \cdots + x_{m},10}} =\sum_{x_{1}\ =\ 1}^{2}\ldots\sum_{x_{m}\ =\ 1}^{2} \oint_{\verts{z}\ =\ a}{1 \over z^{-x_{1} - \cdots - x_{m} + 11}} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ a}{1 \over z^{11}}\pars{\sum_{x\ =\ 1}^{2}z^{x}}^{m} \,{\dd z \over 2\pi\ic} =\dsc{\oint_{\verts{z}\ =\ a}{1 \over z^{11}}\pars{z + z^{2}}^{m} \,{\dd z \over 2\pi\ic}} =\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{m} \over z^{11 - m}} \,{\dd z \over 2\pi\ic} \\[5mm]&={m \choose 10 - m} \end{align}

\begin{align} \sum_{m\ =\ 5}^{10}{m \choose 10 - m} &={5 \choose 5} +{6 \choose 4} + {7 \choose 3} + {8 \choose 2} + {9 \choose 1} + {10 \choose 0} \\&=1 + 15 + 35 + 28 + 9 + 1 \\ &=89 \end{align} which is a sum of a "shallow" diagonal of Pascal's triangle.

It's interesting to see the relation to the Fibonacci Numbers. For this purpose we'll take $0 < a < \dfrac 1\varphi$, where $\ds{\varphi \equiv {1 + \root{5} \over 2}}$ is the Golden Ratio, and sum over $m \geq 1$ in the $\ds{\dsc{\mbox{above red expression}}}$ as follows:

\begin{align}&\color{#66f}{\sum_{m = 1}^{\infty}{\binom{m }{10 - m}}} =\sum_{m = 1}^{\infty} \dsc{\oint_{\verts{z}\ =\ a}{1 \over z^{11}}\pars{z + z^{2}}^{m} \,{\dd z \over 2\pi\ic}} =\oint_{\verts{z}\ =\ a}{1 \over z^{11}}{z + z^{2} \over 1 - \pars{z + z^{2}}} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ a}\pars{{1 \over z^{11}} + {1 \over z^{10}}}\ \underbrace{z \over 1 - z - z^{2}}_{\dsc{\sum_{n\ =\ 0}^{\infty}F_{n}z^{n}}}\ \,{\dd z \over 2\pi\ic} \end{align} $\ds{F_{n}}$ is the $n$-Fibonacci Number and $\ds{z\pars{1 - z - z^{2}}^{-1}}$ is its generating function.

Then, \begin{align}&\color{#66f}{\large\sum_{m\ =\ 1}^{\infty}{m \choose 10 - m}} =\sum_{n\ =\ 0}^{\infty}F_{n}\ \overbrace{% \oint_{\verts{z}\ =\ a}\pars{{1 \over z^{11 - n}} + {1 \over z^{10 - n}}} \,{\dd z \over 2\pi\ic}}^{\dsc{\delta_{n,10} + \delta_{n,9}}}\ =\ F_{10} + F_{9} \\[5mm]&=\color{#66f}{\Large F_{11}} = \color{#66f}{\Large 89} \end{align}