Ta thấy n = 1,2 thỏa mãn. Xét [TEX]n \geq 3[/TEX]
Đặt [tex]x=3+\sqrt{5},y=3-\sqrt{5}\Rightarrow s=x+y=6,p=xy=4[/tex]
Đặt [tex]u_n=x^n+y^n \Rightarrow u_1=s=6,u_2=x^2+y^2=s^2-2p=28[/tex]
Giả sử [tex]u_{n-2},u_{n-1}[/tex] là số nguyên.
Với [tex]u_n=x^n+y^n=(x^{n-1}+y^{n-1})(x+y)-xy^{n-1}-x^{n-1}y=6u_{n-1}-xy(x^{n-2}+y^{n-2})=6u_{n-1}-4u_{n-2}[/tex] cũng là số nguyên.
Vì [tex]u_0,u_1[/tex] là số nguyên nên theo nguyên lí quy nạp 2 bước nhảy ta có đpcm.