You need to distinguish between knowing what to prove and actually proving it.
Actual proofs can be required to be rigorous, but there is no standard of rigor for finding out what to prove. Any kind of hunches, sloppy notation, and weird intuitive leaps are allowed in that phase as long as the actual proof you do at the end is rigorous.
It is very easy to prove -- with all the rigor you'd care to demand -- the fact that $h(n) = 1+3n$ is a solution to your condition, and in fact the only solution on $\mathbb N$.
But here you are instead demanding to have some kind of rigor in knowing that it would be a good idea to attempt such a proof. This demand is foreign to mathematics, and you will run yourself into numerous dead ends in your mathematical education if you keep expecting such demands to be satisfiable.
Your confusion is unfortunately not uncommon among students who have gotten an impression from school that mathematics is about following particular procedures for each problem type. You then get confused when you're asked to investigate a problem without having a procedure to follow. But there are no procedures in general -- to the extent mathematics is about rules at all, it is about investigating what the rules will let you get away with, not about letting the rules tell you what to do with them.
For the concrete question, we could point you towards a general step-by-step procedure for solving linear recurrences. And we could even prove rigorously that said procedure works in general -- but you could still complain that one needs to "guess" a description of that procedure before one can start proving that it works.