# What is the solution to $F\left(n\right)=F\left(n-1\right)+\left(\frac{2}{n}\right)F\left(n-2\right)$ with Legendre symbol?

The recurrence $F\left(n\right)=F\left(n-1\right)+\left(\frac{2}{n}\right)F\left(n-2\right)$ was proposed here

Because of the way the question was formatted, a commenter asked if the $\left(\frac{2}{n}\right)$ meant the Legendre symbol. The proposer said no, it was just ordinary division.

That made me wonder, suppose the Legendre symbol was meant. What would the solution be?

So that is my question.

I have no idea how to solve it.

• Not too familiar with this, but isn't Legendre symbol only defined for odd prime numbers? So it would be undefined for many values of $n$. I don't think this could work but I'm no expert – m1cky22 Aug 2 '16 at 18:47
• We may take $\left( \frac{2}{n} \right)$ as the Jacobi symbol, but there are still issues if $n$ is even. Besides that, it should lead to a complicated hybrid between the Cauchy and Dirichlet convolutions, with very little chances to have a nice closed form. Not that interesting. – Jack D'Aurizio Aug 2 '16 at 18:51
• @m1cky22 You could use the generalization (the Jacobi symbol), which is the product of Legendre symbols for each prime $p$ of $n$ (raised to the appropriate powers). According to Wolfram Alpha, for even $n$ the result is shown as $0$ but I don't know if that necessarily makes sense because the Legendre symbol is not defined for $p=2$. – user51819 Aug 2 '16 at 18:53
• One can instead use the Kronecker symbol to generalize to all integers $n$ – JasonM Aug 2 '16 at 19:00