Hello again,
So, as to write a short tutorial about this problem, we first read the statement again, putting key points in bold:
A patient has N pills to take. Each day he can take either 1 pill or 2 pills until all pills are gone. What will be the total number of different ways of taking N pills?
I have put in bold the statement “each day”, because actually, if you think on it carefully, the number of days that the patient takes is irrelevant as he/she only wants to have N total pills taken, with the restriction that he/she can only take either 1 pill or 2 pills per day.
So the patient can take two days OR one day to have 2 pills (either he has one pill per day during two days, or he has two pills on the first day).
Having this knowledge with us, we can actually rephrase the statement into a more well-known classical problem:
Given an integer N, how many different ways are there to obtain it if we can only use the numbers 1 and 2?
It turns out that the answer to this problem is precisely F(N), where F(N) is the N-th Fibonacci number.
N = 1 --> There is only one way;
N = 2 —> There are two ways: 1+1 or 2;
N = 3 —> There are 3 ways: 1+1+1, 1+2, 2+1;
If you look more closely at these three cases, you can see that F(3) = F(2) + F(1).
From here, the generalization is obvious
Hope this helps!
Best regards,
Bruno