I came across Moser's circle problem not to long ago as an example of where you shouldn't assume that a pattern continues just because it works for the first few values. (The wrong pattern being that the areas created are $2^{n-1}$ where n is the number of points, starting at 1)
I've seen many examples of proofs that the solution is actually ${n\choose 4} + {n\choose 2} + 1$ however I'm struggling to prove that the answer is not $2^{n-1}$.
I attempted a proof by induction.
Base case: $$2^{1-1} = 2^0 = 1$$ Which is correct for 1 point there is 1 area. The problem is the step case.
Step case:
Assume that $2^{k-1}$ gives the number of areas
$$2^{k - 1} + a = 2^{(k+1)-1}$$
... The problem is what is $a$? See I could use the actual proof from above and set $$a = ({(k+1)\choose 4} + {(k+1)\choose 2} + 1) - ({k\choose 4} + {k\choose 2} + 1)$$ but I feel that would be cheating considering it requires knowledge that there is another solution out there. If we didn't know the proof existed and we were looking at this problem for the first time, and we were just trying to prove that our assumption that $2^{n-1}$ was correct (which we know in hindsight that it isn't) I'm not sure how we would go about figuring out what the value of $a$ is. Is there a solution to the problem of what $a$ is? Or is there another proof (excluding proof by exhaustive search) that would show that our logic is wrong here? Thanks