Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an integer $n ≥ 1$, let $f_n$ be the number of lists whose elements all equal $1$ or $2$ and add up to $n−1$. For example $f_1 = 1 = f_2$ because only the empty list ($0$ ones and $0$ twos) sums to $0$ and only a single one sums to $1$. The lists $1,2;\, 2,1;\, 1,1,1$ show us that $f_4 = 3$.

(a) Show that $f_{n+2} = f_{n+1} + f_n$ and hence that $f_1, f_2,...$ is the Fibonacci sequence.

(b) How many lists of ones and twos are there that add up to $10$ and contain $3$ twos?

share|improve this question
add comment

4 Answers 4

up vote 0 down vote accepted

Given a list of $1$s and $2$s adding up to $n-1$, we can append a $2$ to the end of that list to get one adding up to $n+1$. Given a list of $1$s and $2$s adding up to $n$, we can append a $1$ to the end of that list to get one adding up to $n+1$. The lists obtained in this way are uniquely determined by the lists we started from. (Why?) Hence, $$f_{n+2}\geq f_{n+1}+f_n.$$ On the other hand, given a list of $1$s and $2$s adding up to $n+1$, removing the last number on the list will give us one adding up to $n$ or $n-1$. Hence, $$f_{n+2}\leq f_{n+1}+f_n,$$ and so $$f_{n+2}=f_{n+1}+f_n.$$


A list of $1$s and $2$s adding up to $10$ and having $3$ $2$s will necessarily have $7$ total entries. (Why?) Such a list is moreover completely determined by the placement of the $2$s. Since there are $7$ spots and $3$ $2$s to place, there are $\binom{7}{3}=35$ such lists.

share|improve this answer
    
can you please help me solve this Consider the finite sum S=1+2x+3x^(2)+4x^(3)+____+nx^(n-1) Calculate S − xS and hence give a closed expression for S? –  ofo Feb 24 '13 at 19:36
    
The site will only allow you to ask $6$ questions in a given $24$-hour period. If you wait until tomorrow, you can post that as a question. –  Cameron Buie Feb 24 '13 at 20:58
add comment

The first question has appeared several times on MSE.

For the second, there is some ambiguity: Do we mean contain (i) exactly $3$ twos or (ii) at least $3$ twos?

For (i), if there are exactly $3$ twos, then there must be $4$ ones, a total of $7$ digits. The locations of the twos can be chosen in $\dbinom{7}{3}$ ways. After the location of the twos is determined, the ones have to occupy the remaining slots. Calculate: there are $35$ choices.

For interpretation (ii), we are allowed to have $3$ twos, or $4$, or $5$. The analysis is much the same as for interpretation (i), except that we get $\dbinom{7}{3}+\dbinom{6}{4}+\dbinom{5}{5}$.

share|improve this answer
    
can you please help me solve this Consider the finite sum S=1+2x+3x^(2)+4x^(3)+____+nx^(n-1) Calculate S − xS and hence give a closed expression for S? –  ofo Feb 24 '13 at 19:36
    
To do it in the style they ask for, note that $xS=x+2x^2+3x^3+\cdots +nx^n$. Now calculate $S-xS$. This is $(1+2x+3x^2+\cdots+nx^{n-1})-(x+2x^2+\cdots+(n-1)x^{n-1}+nx^n)$. Look at the terms. We get a $1$. Also a $2x-x$. Also a $3x^2-2x^2$, and so on. We end up with (check it) $1+x+x^2+\cdots +x^{n-1}-nx^n$. The first part is a finite geometric series, with sum $\frac{1-x^n}{1-x}$, if $x\ne 1$. So we end up with $(1-x)S=\frac{1-x^n}{1-x}-nx^n$. Divide by $1-x$ to get $S$. –  André Nicolas Feb 24 '13 at 19:50
    
thank you very much –  ofo Feb 24 '13 at 20:06
    
@Aka: You are welcome. But in general I would prefer not to type much mathematics in comments, the editing facilities are poor, the length severely limited. –  André Nicolas Feb 24 '13 at 20:42
add comment

(a) should come from the fact that when you delete the final element of a list which sums to $n+2$ you may end up with a list that sums to $n+1$ (if you deleted a $1$) or to $n$ (if you deleted a $2$).

As to (b), you are talking of lists of length $7$, containing four $1$ and three $2$. This should be stars and bars (Theorem Two) which yields $$ \binom{4 + 4 - 1}{4} = \binom{7}{4} = 35. $$ That is, you have to put your four $1$ in four bins (separated by the three $2$), and some bin may be empty.

PS I have read the post of @AndréNicolas. I have intended question (b) as requiring exactly three $2$.

share|improve this answer
    
can you please help me solve this? Consider the finite sum S=1+2x+3x^(2)+4x^(3)+____+nx^(n-1) Calculate S − xS and hence give a closed expression for S? –  ofo Feb 24 '13 at 19:35
    
@Aka, please post a separate question if you wish. Comments are not the place to start new questions. –  Andreas Caranti Feb 24 '13 at 19:37
    
i tried posting but the website didnt accept my question post –  ofo Feb 24 '13 at 19:39
add comment

Let $L_k$ the set of lists whose elements all equal $1$ or $2$ and add up to $k$. You want to show that $f_n=|L_n|$.
Note that $\ell\in L_{n-2}\Rightarrow \text{append}(\ell,2)\in L_n$ and $\ell \in L_{n-1}\Rightarrow \text{append}(\ell,1)\in L_n$. Conclude that $|L_{n-2}|+|L_{n-1}|\leq |L_{n}|$...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.