$(1$ point$)$ Alice has an infinite amount of $$6$ coins and $$10$ and $$15$ bills. Use induction to prove that Alice can form any amount of at least $$30$ using these. For example, Alice can form $$31$ by taking one of each, or she can form $$32$ by taking two $$10$ bills and two coins.

A hint$/$clarification for PS$1-$P$7$

I have removed the word 'strong' from the question so that you can prove it using any type of induction you like. We haven't covered any examples of strong induction in the lectures, but we will soon. If you are stuck, here are a few hints, depending on what type of induction you want to write the proof in:

General hint:

$,$ The formal statement you want to prove is: for all ninN, if $n30,$ then there exist naturals $s,t,u$ such that $n=15t+10s+6u.$

For weak induction:

The base case is easy.

For the inductive step, consider the main cases $t>0,$ and then $t=0,$ and its subcases $s=0,1$ and $u=0,1,2,3$ separately.