rsolve gives None for linear homogeneous recurrence relation

[Smit-create]

>>> from sympy import rsolve, Function, symbols
>>> n = symbols('n', integer=True)
>>> F = Function('F')
>>> eq = F(n+3) - 3*F(n+1) + 2*F(n)
>>> print(rsolve(eq, F(n), {F(1):0, F(2):8, F(3):-2}))
None

While this works when we don't pass initial condition as:

>>> print(rsolve(eq, F(n)))
(-2)**n*C0 + C1*(C0 + C1*n)/C0

Expected answer: F(n) = 2*n + (-2)**n

[naveensaigit]

The issue here is that solve is unable to find values of C0 and C1-

sympy/sympy/solvers/recurr.py

Lines 820 to 825 in c3087c8

	result = solve(equations, *symbols)
	if not result:
	return None
	else:
	solution = solution.subs(result)

We could raise a warning saying sympy is unable to solve for the constants and return the general solution. That would be more helpful than just returning None

[oscarbenjamin]

The equations for C0 and C1 do not have any solution. Are they correct?

The equations are:

(Pdb) p equations
[-2*C0 + C1*(C0 + C1)/C0, 4*C0 - 8 + C1*(C0 + 2*C1)/C0, -8*C0 + 2 + C1*(C0 + 3*C1)/C0]
(Pdb) p symbols
[C0, C1]

That is:

In [79]: equations = [-2*x + y*(x + y)/x, 4*x - 8 + y*(x + 2*y)/x, -8*x + 2 + y*(x + 3*y)/x]                                      

In [80]: equations                                                                                                                
Out[80]: 
⎡       y⋅(x + y)            y⋅(x + 2⋅y)             y⋅(x + 3⋅y)⎤
⎢-2⋅x + ─────────, 4⋅x - 8 + ───────────, -8⋅x + 2 + ───────────⎥
⎣           x                     x                       x     ⎦

In [81]: solve(equations, [x, y])                                                                                                 
Out[81]: []

[naveensaigit]

The equations for C0 and C1 do not have any solution. Are they correct?

Yes, they don't have a solution and I verified the same on Wolfram. However, Wolfram is still able to solve the recurrence relation and reports the correct answer - Try this
I think we're missing something here.

[oscarbenjamin]

Why are there three equations for two symbols?

If this is a third order recurrence then there should be three arbitrary constants. Perhaps this is related to the problem in #17982

[oscarbenjamin]

The symbols come from here:

sympy/sympy/solvers/recurr.py

Lines 617 to 624 in bd327ec

	for z in roots(poly, Z).keys():
	if z.is_zero:
	continue
	(C, s) = rsolve_poly([polys[i].as_expr()*z**i for i in range(r + 1)], 0, n, symbols=True)
	if C is not None and C is not S.Zero:
	symbols |= set(s)

The poly there has a multiple root:

(Pdb) p poly
_Z**3 - 3*_Z + 2
(Pdb) p roots(poly, Z)
{-2: 1, 1: 2}

That also happens with the example from #17982:

(Pdb) p poly
_Z**3 + 10*_Z**2 + 32*_Z + 32
(Pdb) p roots(poly, Z)
{-2: 1, -4: 2}

Maybe the problem is that multiple roots are not handled. Looping over roots(poly, Z).keys() ignores the multiplicity of the roots.

[naveensaigit]

Yes, currently sympy is not able to solve linear recurrences with order>=2 properly. Some other related issues are #8697, #11261. Infact, some equations with order 1 are also a problem as mentioned in #13629. I think most of the issues from rsolve arise from the mistake you pointed out. I'll see how it can be fixed.

[naveensaigit]

This can be closed now

[oscarbenjamin]

Oh yes, thanks.