Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps. I know this question has been posted before, there is a solution in my text-book for this question and also this is posted on so many websites with full solution but I still don't understand. So can someone please help me?
BASIS STEP: We can form postage of 12, 13, 14, and 15 cents using three 4-cent stamps, two
4-cent stamps and one 5-cent stamp, one 4-cent stamp and two 5-cent stamps, and three 5-cent
stamps, respectively. This shows that P (12), P (13), P (14), and P (15) are true. This completes
the basis step.
INDUCTIVE STEP: The inductive hypothesis is the statement that P (j )is true for 12 ≤ j ≤ k,
where k is an integer with k ≥ 15. To complete the inductive step, we assume that we can form
postage of j cents, where 12 ≤ j ≤ k. We need to show that under the assumption that P (k + 1)
is true, we can also form postage of k + 1 cents. Using the inductive hypothesis, we can assume
that P (k − 3) is true because k − 3 ≥ 12, that is, we can form postage of k − 3 cents using
just 4-cent and 5-cent stamps. To form postage of k + 1 cents, we need only add another 4-cent
stamp to the stamps we used to form postage of k − 3 cents. That is, we have shown that if the
inductive hypothesis is true, then P (k + 1) is also true. This completes the inductive step.
I am stuck at this part:
how did they get k> 15 ? 
and i don't get how did they get P(k-3) 
like can someone please explain this to me?
 A: Another proof, which looks more intuitive for me. Let's assume we have a set of stamps to form the $k$ total. Let's denote $n$ and $m$ a number of 4-cents and 5-cents stamps correspondingly.
$$n \cdot 4 + m \cdot 5 = k$$
We need to prove that we can make changes in this set to form the next amount $k + 1$. There are two cases. If $n$ > 0, then we'll replace one 4-cents stamp by one 5-cents stamp and get the next amount:
$$(n - 1) \cdot 4 + (m + 1) \cdot 5 = k + 1$$
If $n = 0$, then we'll replace three 5-cents stamps by four 4-cents stamps and again get the next amount:
$$(m - 3)\cdot 5 + 4 \cdot 4 = k + 1$$
Of course, in the second case we have to have $m \ge3$, that's why we need $k \ge 15$.
A: How comfortable are you with induction?
Base cases: $n = 12,13,14,15$ we can get $P(n)$.
Induction step:  Suppose we can do it for all cases for $n = 12,13,.....,k\ge 15$.  (Which we can if $k = 15$)
We need to show we can do it for $k+1$.
Well $k \ge 15$ so $k-3 \ge 12$ so we can do it for $P(k-3)$
That is we can find $a,b$ so that $k - 3 = 4a + 5b$.
To do $P(k+1)$ we can do $k + 1 = (k-3) + 4 = 4(a + 1) + 5b$.
And that's it.  We've proven if we can do  $P(k)$ then we can do  $P(k+1)$. 
So by induction we can do it for all $n \ge 15$ as well as for $n = 12,13,14,15$ so we can do it for $n \ge 12$.
A: Assume a property is true for $0$, and we write $P(0)$; assume also that $\forall n\in\mathbb{N},P(n)\implies P(n+1)$ that is every time $P$ is true for $n$, it's also true for $n+1$. The induction principle states that $P$ is true for all the natural numbers, because $P(0)$ holds for the basis step and then, using the induction step, $P(0)\implies P(1)\implies P(2)\implies...$.
This is the most basic form of induction, and as you can see the basis step being on $0$ is totally arbitrary: you can prove that $P(12)$ is true, and then you get the implications chain $P(12)\implies P(13)\implies...$, that is you have proved that the property holds for every number $\ge 12$.
Let's imagine now that you have proved that $\forall n\in\mathbb{N},P(n)\implies P(n+2)$ - where $2$ is just an example - and $P(0)$. Can you conclude that $P$ holds for all the natural numbers? No, you can just deduce that $P(0)\implies P(2)\implies P(4)\implies...$ that is your property holds for all the $even$ numbers. But if you could also prove $P(1)$, then you would also get $P(1)\implies P(3)\implies P(5)\implies...$ and so $P$ would hold for $odd$ numbers too.
Now, your problem talks about postage $\ge 12$, so it would have no sense trying to prove that property for - let's say - $5$, so they have shown as basis step $P(12), P(13), P(14), P(15)$. Why four of them and not just one?
Look at the inductive step. You want to prove that $P(k)\implies P(k+1)$, so assume $P(n),\forall n\le k$ and let's see if we can deduce $P(k+1)$. Take postage for $k+1$ and $k+1=(k-3)+4$, that is you can get $k+1$ adding a 4-cent stamp to a $k-3$ postage: if you have $P(k-3)$, you get also $P(k+1)$.
You have already proved $P(12)-P(15)$ by hand. Fix $k=15$, so $k+1=16$: we know that if $P(k-3)$ holds, then $P(k+1)$, but $P(k-3)=P(12)$ and this is true! So $P(16)$ holds.
Now $k=16$ and $k+1=17$, $k-3=13$. $P(k-3)=P(13)$ is true, so $P(k+1)=P(17)$ holds. The same goes for $P(14)\implies P(18)$ and $P(15)\implies P(19)$. We have used all the basis steps, and now we get $P(16)\implies P(20)$, $P(17)\implies P(21)$ and so on.
A: The main question here is, why $4$ cases in the basic step. @Angelo Randina's answer explains this. I will, here, try to explain the problem that will arise if we don't do the 4 base cases.
Basic Step: $P(12) = 4\times 3$ or four stamps of 3 cents
Inductive Step: Now, since we have only done the basic step for $P(12)$, we will have to let $12\le k$ instead of $15\le k$ as it was done with the $4$ base cases. Now, since $k\ge 12$, so $k-3\ge9$. It means that $k-3$ may fall below $12$. This is the problem because now we cannot argue that $P(k-3)$ is true all the time because it is not true when $k-3<12$.
Since, we cannot argue that $P(k-3)$ is true, we cannot say that $P(k+1) = P(k-3) + 4$. So we have only two options 1) Either, we do $4$ base cases and let $k\ge15$ and get to $P(k+1) = P(k-3) + 4$ or 2) we do $5$ base cases and let $k\ge 16$ and get to $P(k+1) = P(k-4)+5$
Here, we can see how many base cases have to be solved is derived solely by the value of the postage stamp. If the minimum value postage stamp is $4$ cents, then we need at least $4$ base cases.
Another Example: To see this, consider another example, every amount of postage greater than $12$ cents can be paid just by $3$ cents and $7$ cents stamps. Here, the minimum value of a stamp is $3$ cents so we need $3$ base cases and we will let $k\ge 12+3-1=14$ so that we can get to $P(k+1) = P(k-2) + 3$. So, lets do the basic and inductive steps
Basic Step:
$P(12) = 4\times 3$, i.e using four $3$ cents stamps
$P(13) = 2\times 3 + 1\times 7$, i.e using two $3$ cents stamps and one $7$ cents stamp
$P(14) = 2 times 7$, i.e using two $7$ cents stapms
Inductive Step:
Assume $12\le j\le k, P(j)$ and prove $P(k+1)$. We can get to $P(k+1)$ by going back two steps adding a $3$ cents stamp, i.e $P(k+1) = P(k-2)+3$ because we are sure that $k-2\ge 12$ and we have assumed $\forall j>12 P(j)$
