Strong Induction :
$(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x)) \rightarrow (\forall x)P(x)$.
To prove it from Induction , we have to define $Q(x) := (\forall z)(z \le x \rightarrow P(z))$ and apply Induction to $Q(x)$.
See Elliott Mendelson, Introduction to mathematical logic (4ed - 1997), PROPOSITION 3.9, page 166 :
Proof
(A)
(i) $(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x))$ --- assumed
(ii) $(\forall z)(z < 0 \rightarrow P(z)) \rightarrow P(0))$ --- from (i) by $\forall$-elim
(iii) $(\forall z)\lnot (z < 0)$ --- provable from axioms
(iv) $(\forall z)(z < 0 \rightarrow P(z))$ --- from tautology : $\lnot A \rightarrow (A \rightarrow B)$ and (iii) and $\forall$-intro
(v) $P(0)$ --- from (ii) and (iv) by modus ponens
(vi) $(\forall z)(z \le 0 \rightarrow P(z))$ --- from the fact that : for any natural number $k$ and any formula $\varphi$, $\varphi(0) \land \varphi(1) \land \ldots \land \varphi(k) \leftrightarrow (\forall x)(x \le k \rightarrow \varphi(x))$.
But (vi) is $Q(0)$; thus, from (i)-(vi) we have :
$(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x)) \vdash Q(0)$.
(B)
In the same way, we prove that from assumptions : $(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x))$ and $Q(x)$, $Q(x')$ follows [where $x'$ is $S(x)$, the "successor" of $x$].
Thus, by Deduction Theorem :
$(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x)) \vdash (\forall x)(Q(x) \rightarrow Q(x'))$.
By (A), (B) and Induction, we obtain $(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x)) \vdash (\forall x)Q(x)$, that is :
$(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x)) \vdash (\forall x)(\forall z)(z \le x \rightarrow P(z))$.
Hence, by rule $\forall$-elim twice , $(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x)) \vdash (x \le x \rightarrow P(x))$.
But we have : $\vdash x \le x$.
Thus, $(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x)) \vdash P(x)$; by $\forall$-intro and the Deduction theorem :
$(\forall x)((\forall z)(z < x \rightarrow P(z)) \rightarrow P(x)) \vdash (\forall x)P(x)$.
For each $n\geq 0$, let $S(n)$ denote the statement
$$
S(n) : F_n+2F_{n+1}=F_{n+3}.
$$
First note that $S(n)$ has a rather trivial direct proof:
$$
F_{n+3} = F_{n+1}+F_{n+2} = F_{n+1}+(F_n+F_{n+1})=F_n+2F_{n+1}.
$$
Thus, it is really not necessary to prove your statement by using induction, but let's do it anyway since we're on the topic.
Base step: $S(0)$ says $F_0+2F_1=F_3$, which is true since $F_0=0, F_1=1$, and $F_3=2$.
Inductive step: For some fixed $k\geq 0$, assume that $S(k)$ is true. To be shown is that
$$
S(k+1) : F_{k+1}+2F_{k+2} = F_{k+4}
$$
follows from $S(k)$. Note that $S(k+1)$ can be proved without the inductive hypothesis; however, to formulate the proof as an inductive proof, following sequence of equalities uses the inductive hypothesis:
\begin{align}
F_{k+1}+2F_{k+2} &= F_{k+1}+2(F_k+F_{k+1})\\[0.5em]
&= (F_{k+1}+F_k)+(F_k+2F_{k+1})\\[0.5em]
&= F_{k+2}+(F_k+2F_{k+1})\\[0.5em]
&= F_{k+2}+F_{k+3}\qquad\text{by $S(k)$}\\[0.5em]
&= F_{k+4}.
\end{align}
This completes the inductive step $S(k)\to S(k+1)$.
Thus, by mathematical induction, $S(n)$ is true for every $n\geq 0$. $\Box$
Best Answer
First, let us "scale down" the problem by a factor of $5$, i.e., that we are working with $5$ and $8$ gift certificates. We will "scale up" our solution afterwards.
Notice that $5$ and $8$ are coprime and thus their non-negative integer linear combinations form a numerical semigroup with two generators. A nice result of numerical semigroups with two generators $m,n$ is that any number bigger than $mn-m-n$ is in the semigroup.
To show this by induction for this particular problem, notice that $mn-m-n = 8*5-8-5 = 27$ is the largest number that can't be written as a positive integer linear combination of $5$ and $8$. Thus, the next $5$ numbers ($28,29,30,31,32$) can be written as a linear combination of $5$ and $8$, this will form your base case. See if you can explicitly find the linear combinations of $5$ and $8$ that will give you those five numbers. Now, consider $n>32$ and suppose that $k$ can be written as a positive integer linear combination of $5$ and $8$ for all $28 \leq k < n$. We want to show the same holds for $n$. Notice that $28 \leq n-5 < n$ and thus $n-5 = 5a+8b$ for $a,b\in \mathbb{Z}^+$. From this, we see that $n= 5(a+1)+8b$ and thus we can write $n$ as a positive integer linear combination of $5$ and $8$, thus completing the induction.
We still need to check the values less than $28$ which we can do by brute force. We see that we can get the following with positive integer linear combinations of $5$ and $8$ for numbers less than $28$, $$\{ 0,5,8,10,15,16,18,23,24,25,26\}.$$
Scaling our solution up by $5$, we can obtain the following amounts: $$\{0,25,40,50,75,80,90,115,120,125,130\} \cup \{140, 145,150,\dots\}$$