Repository: sympy/sympy
File: sympy/solvers/tests/test_recurr.py (Python)

Code before:

    assert rsolve_hyper([-1, 1], 1 + n, n).expand() == C0 + n**2/2 + n/2

    assert rsolve_hyper([-1, 1], 3*(n + n**2), n).expand() == C0 + n**3 - n

    assert rsolve_hyper([-a, 1],0,n).expand() == C0*a**n

    assert rsolve_hyper([-a, 0, 1], 0, n).expand() == (-1)**n*C1*a**(n/2) + C0*a**(n/2)

    assert rsolve_hyper([1, 1, 1], 0, n).expand() == \
        C0*(Rational(-1, 2) - sqrt(3)*I/2)**n + C1*(Rational(-1, 2) + sqrt(3)*I/2)**n

    assert rsolve_hyper([1, -2*n/a - 2/a, 1], 0, n) == 0

    # issue 27901
    assert rsolve_hyper([-2*2**n, 2*2**n], -2*binomial(n, k) + binomial(n + 1, k), k) is None
    assert rsolve_hyper([-1, 1], factorial(n**2), n) is None
    assert rsolve_hyper([-1, 1], n**n, n) is None
    assert rsolve_hyper([-1, 1], sqrt(n), n) is None

    assert rsolve_hyper([-2, 1], 2**(n**3 + 1), n) is None
    assert rsolve_hyper([-2, 1], 2**(a*n + 1), n) is None

    assert rsolve_hyper([-1, 1], fibonacci(n), n) is None
    assert rsolve_hyper([-1, 1], euler(n), n) is None
    assert rsolve_hyper([-1, 1], harmonic(n), n) is None

@XFAIL
def test_rsolve_ratio_missed():
    # this arises during computation
    # assert rsolve_hyper([-1, 1], 3*(n + n**2), n).expand() == C0 + n**3 - n
    assert rsolve_ratio([-n, n + 2], n, n) is not None


def recurrence_term(c, f):
    """Compute RHS of recurrence in f(n) with coefficients in c."""
    return sum(c[i]*f.subs(n, n + i) for i in range(len(c)))


def test_rsolve_bulk():
    """Some bulk-generated tests."""
    funcs = [ n, n + 1, n**2, n**3, n**4, n + n**2, 27*n + 52*n**2 - 3*
        n**3 + 12*n**4 - 52*n**5 ]
    coeffs = [ [-2, 1], [-2, -1, 1], [-1, 1, 1, -1, 1], [-n, 1], [n**2 -
        n + 12, 1] ]
    for p in funcs:
        # compute difference
        for c in coeffs:
            q = recurrence_term(c, p)
            if p.is_polynomial(n):
                assert rsolve_poly(c, q, n) == p

Review comment (suggestion):
Are these all examples that should really not be None if hypersimp was improved? There should at least be some explanation in comments about this.

Use a URL to reference issues. The issue you are referencing has no explanation of these examples. It would be better to explain them in https://github.com/sympy/sympy/issues/27975

Code after:

    assert rsolve_hyper([-1, 1], 1 + n, n).expand() == C0 + n**2/2 + n/2

    assert rsolve_hyper([-1, 1], 3*(n + n**2), n).expand() == C0 + n**3 - n

    assert rsolve_hyper([-a, 1],0,n).expand() == C0*a**n

    assert rsolve_hyper([-a, 0, 1], 0, n).expand() == (-1)**n*C1*a**(n/2) + C0*a**(n/2)

    assert rsolve_hyper([1, 1, 1], 0, n).expand() == \
        C0*(Rational(-1, 2) - sqrt(3)*I/2)**n + C1*(Rational(-1, 2) + sqrt(3)*I/2)**n

    assert rsolve_hyper([1, -2*n/a - 2/a, 1], 0, n) == 0

    # issue 27901
    assert rsolve_hyper([-1, 1], factorial(n**2), n) is None
    assert rsolve_hyper([-1, 1], n**n, n) is None
    assert rsolve_hyper([-1, 1], sqrt(n), n) is None
    assert rsolve_hyper([-1, 1], 1/k, k) is None

    assert rsolve_hyper([-2, 1], 2**(n**3 + 1), n) is None
    assert rsolve_hyper([-2, 1], 2**(a*n + 1), n) is None

    assert rsolve_hyper([-1, 1], fibonacci(n), n) is None
    assert rsolve_hyper([-1, 1], euler(n), n) is None
    assert rsolve_hyper([-1, 1], harmonic(n), n) is None
    assert rsolve_hyper([-(2*k - 1), 1], 1, k) is None

@XFAIL
def test_rsolve_ratio_missed():
    # this arises during computation
    # assert rsolve_hyper([-1, 1], 3*(n + n**2), n).expand() == C0 + n**3 - n
    assert rsolve_ratio([-n, n + 2], n, n) is not None


def recurrence_term(c, f):
    """Compute RHS of recurrence in f(n) with coefficients in c."""
    return sum(c[i]*f.subs(n, n + i) for i in range(len(c)))


def test_rsolve_bulk():
    """Some bulk-generated tests."""
    funcs = [ n, n + 1, n**2, n**3, n**4, n + n**2, 27*n + 52*n**2 - 3*
        n**3 + 12*n**4 - 52*n**5 ]
    coeffs = [ [-2, 1], [-2, -1, 1], [-1, 1, 1, -1, 1], [-n, 1], [n**2 -
        n + 12, 1] ]
    for p in funcs:
        # compute difference
        for c in coeffs:
            q = recurrence_term(c, p)
            if p.is_polynomial(n):