The general formula won't come, so you don't start.
Computing $n=1,2,3$ is exploration, not cheating. Small cases reveal the structure you then prove properly. The signal to try it: a claim about every $n$ with no recurrence in sight.
Next time: When the general case won't come, work three small ones.