STRONG INDUCTION

Prove the following statements by strong induction:

Prove that every positive natural number can be written as a sum of powers of two. $($This is the way integers are represented in computer science $-$ as a binary string.$)$

Prove that for every natural number $n12$ there exist $a,$binN such that $n=4a+5b.($Hint: You may need a base case where nin$\{12,13,14,15\}.)$

Correction: The question should say "there exist $a,$bin$u\{0\}"$; that is$,$ the numbers $a,b$ are also allowed to take the value zero.

We are given $n$ identical looking coins, and a scale that allows comparing the weights of two sets of coins $($i$.$e$.,$ we can put any number of coins on each side of the scales$).$ We know that there is exactly one fake coin $-$ it is lighter than other coins. Prove that we can discover the fake coin using $|$~$lo{g}_3(n)$~$|$ comparisons.

$($Example: When $n=3,$ we can discover the fake coin with one comparison. Take any pair of coins and compare their weight: if their weight is identical, then the third coin is the fake one; and otherwise, one coin is lighter than the other, so it must be fake.$)$