I was reading a problem that stated:
There are a certain number of objects all of which have the same weight except for one which has a different weight. In all other aspects the objects are identical. Determine the unique one that has the different weight using a pair of scales optimally. Show by induction on $n$ that at most $2*n$ comparisons are needed to identify the object when the total number of objects is $3^n$
My original thought was that the base case has to be $n = 1$ where we have a total of $3^1$ objects which we can figure out the one we are searching for with 2 comparisons.
But the solution uses as base case $n = 0$ considering in that case that the $3^0 = 1$ object is the one we are searching for. I originally rejected $n = 0 $ as base case because with $1$ object we can't do any comparison so we can't know if it is the one we search for or not.
So my question is: how do we determine in such cases how do we treat the base case? Could we also not have considered that for $n = 0$ the $1$ coin can not be the one we are searching for? Or even that as I originally thought that it is not meaningful to use $n = 0$ as base case?
Is there something in the problems we need to be cautious of, or some convention that exists that helps define the base case?
In this particular problem, it makes me think that there is some subtle implication that the specific unique object under search must be part of the set even if all the rest are missing which I did not pick up.
Is that so? Is there some convention for inductive approaches?
You use whatever works for your base case, then carefully state what you have proved. If you use $n=1$ as your base case, you have not proved the $n=0$ case. You would have to state your result as "For all numbers of objects $n \ge 1$, it takes at most $2n$ comparisons ..."
If I were doing the proof, I would probably start with $n=1$. Having done it, I would think about $n=0$ for completeness and prove the $n=0$ case separately. I would wind up proving $n=0$ and $n=1$ directly, then using induction for everything above $1$. The case of $n=0$ is often different and it can be easier to make the induction work starting from $n=1$.
The base case can be higher yet. One we see here is to prove $n! \gt n^2$ for $n \ge 4$. We can note that the statement is not true for $n=3$ as $3!=6 \not \gt 3^2=9$. You use $4$ as the base case and the induction goes through nicely.