I have a problem that I need to prove by induction and I don't know how..
I have $3^n$ gold coins. All of them weigh the same except one which is lighter than each of the others. Prove that the fake gold can be found within $n$ scale weighings.
Thx for the help (:
Induction:
If $n=1$ it is obvious that it is possible to find the fake coin with $n=1$ times weighing.
Now I assume that there is an $n$ for which it is possible to find the fake coin from a collection of $3^n$ coins with $n$ times weighing. I can do this because I know that there is at least one such $n$ ($n=1$).
So if I know have $3^{n+1}$ coins, I can divide them up in to $3^n$ groups of each $3$ coins. Now you can use the assumption: We know that there must be one lighter group of of coins but all the other groups are the same weight. So we can find the lightest of all the $3^n$ groups with using the scale $n$ times. We now found the lightest group and know that the fake coin must be in there. And we can obviously find the fake coin in this group with weighting once. So we found the fake coin from $3^{n+1}$ coins with using the scale $n+1$ times.
The idea behind that is that we first find a case where our statement is true $(n=1)$ and then show that IF there is an $n$ such that the statement is true, then the statement must be true for $n+1$. We can reasen now that we know that it is true for $n=1$ so it must be true for $n=2$ and because of this it must also be true for $n=3$ etc.