It should be remarked that although the principle of mathematical induction suffices to prove the formula...once this formula has been written down, the proof gives no indication of how this formula was arrived at in the first place; why precisely the expression should be guessed as an expression for the sum of the first n cubes, rather than or or any of the infinitely many expressions of a similar type that could have been considered. The fact that the proof of a theorem consists in the application of certain simple rules of logic does not dispose of the creative element in mathematics, which lies in the choice of the possibilities to be examined. The question of the origin of the hypothesis...belongs to a domain in which no very general rules can be given; experiment, analogy, and constructive intuition play their part here. But once the correct hypothesis is formulated, the principle of mathematical induction is often sufficient to provide the proof. Inasmuch as such a proof does not give a clue to the act of discovery, it might more fittingly be called a verification. --Courant and Robbins, What is Mathematics, Section I.2.4.
In this section we discuss some ways to guess formulas for sequences. (P.S. Courant and Robbins is an excellent book to add to your personal library.)