recurrence relation using generating function

[prisma trench]

I seem to get the answer in complex variables. Please help me out

[graceful quest]

1. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
2. Wait patiently for a helper to come along.
3. Once someone helps you, say thank you and close the thread with:

   +close
   

4. Feel free to nominate the person for helper of the week in #helper-nominations
5. Do not ping the mods, unless someone is breaking the rules. If there is a conflict amongst multiple helpers feel free to ping “Helper Mod”
6. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[prisma trench]

Here's what I've tried

[naive loom]

your expression for the generating function is the right one

and I trust you for partial fraction decomposition

just rewrite each fraction in the form α/(1-x β), then the coefficient of x^n will be equal to α β^n

don't worry if β is a complex number, because α (β^n + β'^n) will be an integer for (β,β') the roots of 1-3x+4x^2 (α is an integer in this case, and β^n + β'^n is a symmetric function of the roots of the polynomial, hence it expresses as a polynomial in the coefficient of the polynomial, which are integers)

@prisma trench

[prisma trench]

Thank you very much

[pallid raft]

@prisma trench has given 1 rep to @naive loom

[prisma trench]

+close