Question

Let $f\left(n\right)$ denotes the number of different ways in which the positive integer $n$ can be expressed as the sum of $1^{\prime }s$ and $2^{\prime }s$. For example $f\left(4\right)=5$, since
$4=2+2=2+1+1=1+2+1=1+1+2=1+1+1+1$.

Then which of the following(s) is (are) CORRECT ?

• A. $f\left(6\right)=13$
• B. $f\left(f\right(6\left)\right)=377$
• C. $f\left(f\right(6\left)\right)=370$
• D. $f\left(6\right)=11$

Answer 1

Answer: (A), (B)

$f\left(f\right(6\left)\right)=377$

$6=0\left(2\right)+6\left(1\right)=1\left(2\right)+4\left(1\right)=2\left(2\right)+2\left(1\right)=3\left(2\right)+0\left(1\right)$

$\therefore$ Total number of permutations
$=\frac{6!}{6!}+\frac{5!}{4!}+\frac{4!}{2!2!}+\frac{3!}{3!}=13\therefore f\left(6\right)=13$

$f\left(f\right(6\left)\right)=f\left(13\right)13=0\left(2\right)+13\left(1\right)=1\left(2\right)+11\left(1\right)=2\left(2\right)+9\left(1\right)=3\left(2\right)+7\left(1\right)=4\left(2\right)+5\left(1\right)=5\left(2\right)+3\left(1\right)=6\left(2\right)+1\left(1\right)$

$\therefore$ Total number of permutations
$=\frac{13!}{13!}+\frac{12!}{11!}+\frac{11!}{2!9!}+\frac{10!}{3!7!}+\frac{9!}{4!5!}+\frac{8!}{5!3!}+\frac{7!}{6!}$

$=1+12+55+120+126+56+7=337\therefore f\left(f\right(6\left)\right)=377$


Alternate solution :
We know that,
$f\left(1\right)=1f\left(2\right)=23=1+1+1;1+2;2+1f\left(3\right)=3f\left(4\right)=55=5\left(1\right);2\left(2\right)+1\left(1\right);1\left(2\right)+3\left(1\right)f\left(5\right)=1+\frac{3!}{2!1!}+\frac{4!}{3!1!}=8$

From the above, we can see a pattern
$f\left(5\right)=f\left(4\right)+f\left(3\right)f\left(n\right)=f(n-1)+f(n-2)$
Therefore, $f\left(6\right)=f\left(5\right)+f\left(4\right)=8+5=13$
$f\left(f\right(6\left)\right)=f\left(13\right)$

Now,
$f\left(13\right)=f\left(12\right)+f\left(11\right)\Rightarrow f\left(13\right)=2f\left(11\right)+f\left(10\right)\Rightarrow f\left(13\right)=3f\left(10\right)+2f\left(9\right)\Rightarrow f\left(13\right)=5f\left(9\right)+3f\left(8\right)\Rightarrow f\left(13\right)=8f\left(8\right)+5f\left(7\right)\Rightarrow f\left(13\right)=13f\left(7\right)+8f\left(6\right)\Rightarrow f\left(13\right)=21f\left(6\right)+13f\left(5\right)\Rightarrow f\left(13\right)=21\times 13+13\times 8\Rightarrow f\left(13\right)=13\times 29=377$