First, by inspection, you can guess that a_(n+2) = 3a_(n+1) + a_n Then, you may prove it by induction as follow, construct sequence {b_n} with b_0=1, b_1=3 and b_(n+2)=3b_(n+1)+b_n, we will show that {a_n}={b_n}. To start with, b_3 = 3(3)+1 = 10, and a_3 = (3^2 + 1)/1 = 10 So a_3 = b_3 Assume for all i