Try induction, it's real easy in this case.
We can prove it by deriving that function ourselves . . .
We have: .
. . and we have: .
. . Then: .
The generating function is of the form: .
We know the first two values of the sequence:
Add  and : .
Substitute into : .