You are given a bag containing 1 and 2 ounce gold rounds.
You need to draw one coin at a time till they Sum up to ten rounds.
How many different ways you can achieve that?
What is the quickest path to calculate?
How about if you are asked to draw till it sums to twenty rounds.
No searches...No calculators..No computers
The number of ways to achieve $10$ ounces is:
the number of ways to achieve $9$ ounces (as you draw the $1$ ounce) + the number of ways to achieve $8$ ounces (or as you draw the $2$ ounce).
To make it general:
$F(N) = F(N-1) + F(N-2)$ with $F(1) = 1$ and $F(2) = 2$ as the base cases.
So:
We may calculate $F(10)$ in bottom-up approach from $F(3) = 2 + 1 = 3$, $F(4) = 3 + 2 = 5$, and so on. Then we have $F(10) = 144$.
Note that:
$F$ is actually a Fibonacci function. So you can use its non-recursive formula to determine $F(N)$.
I used the same approach as athin but I got: 1 2 3 5 8 13 21 34 55 89 giving $89$ for the first answer. Essentially it follows a Fibonacci sequence but shifted by one (Fibonacci starts with 1 1 2, this one starts with 1 2 3).
For the second, using a Fibonacci relationship from here, I got:
$F(20) = F(9)^2 + F(10)^2 = 55^2 + 89^2 =$
(lengthy no calculator math)
$(50+5)^2 + (90-1)^2 =$
$2500 + 500 + 25 + 8100 - 180 + 1 =$
$3000 + 8100 + 25 - 180 + 1 =$
$11100 + 26 - 180 = 10920 + 26 =$
$10946$
As for quickest path to calculate, the site I linked to shows how to compute Fibonacci numbers fast using a doubling method like I used to find F(20).
The sequence is:
$$1+(x+x^2)+(x+x^2)^2+(x+x^2)^3+\dots$$
and we want the coefficient of $x^{10}$.
The sequence equals:
$$\frac{1}{1-x-x^2}$$
which is the;
We therefore want:
$F(10)=89$.
Simplest answer is
To get the number of ways to pick ten rounds is eleventh number of STD Fib sequence..for 20, it is 21st. Even if the seeds of Fib are different..say 3 and 5, no of ways of picking 8, 13, 21 ..so on can be calculated in similar fashion.
