Methods and knowledge needed for the conversion of $\sum$ and $\prod$ into non-iterative expressions

Question

I think this might be a very broad question, but here it goes.

I have made a formula, using a sigma function, to give the $n$th number in a recursive sequence. I'm trying to make it into a non-iterative formula, but my efforts have only lead to formulas with iterative functions within them. I don't want to post these iterative formulas, and ask for the non-iterative version, because I find I learn best when I figure it out myself. So, instead, I am asking for general methods to do this, and for places where I can get the relevant knowledge for tasks like this.

I've read that Conway and Guy wrote a book, The Book of Numbers, with a section dedicated to this subject. However, I'd like to consider some free options before I go ahead and buy this book. After all, it could very well be it is geared towards a higher level of mathematics anyways.

EDIT:

Clarification: My current formula, for the $n$th number in a sequence, uses only $n$ as its input. It is a function of $n$. But it has iteration going on. I want to turn my $g(n)$ into $f(n)$, where $f(n)$ has no iterative operations going on.

Example:

$$\sum_{k=1}^n k= g(n)$$

This is an iterative function for finding the triangular number of $n$. The higher $n$ is, the greater the computation. I want to snip that computation away with a non-iterative formula:

$$\sum_{k=1}^n k = \binom{n+1}{2}$$

$$\binom{n+1}{2} = f(n)$$

So, what are some generally applicable methods to make $g(n)$ into $f(n)$? Where can I read about knowledge pertaining to tasks like these?

Answer 1

This is just the notion of evaluating discrete sums and products. You may achieve this by learning about discrete calculus.

Answer 2

You asked

So, what are some generally applicable methods to make g(n) into f(n)?

What you are looking for, if I understand your question correctly, is a general method for getting a closed form for a finite summation. This is very analogous to the problem of integration of functions in closed form. It all depends on the specific summation you have. If you are summing a polynomial function, the answer depends on Bernoulli numbers (see the Wikipedia article Faulhaber's formula). If you are summing binomial coefficient terms then Wilf-Zeilberger pair is a general method for that.

There are other general methods that are used by Computer Algebra Systems and I suggest that you can try using them on your problem.

Answer 3

A general hint:

If $f(k)$ is a polynomial of degree $d$, then

$$\sum_{k=0}^n f(k)=g(n)$$ is a polynomial of degree $d+1$ with the constant term $f(0)$. You can find this polynomial by Lagrangian interpolation on $d+1$ particular values of $n$, or by solving the recurrence

$$g(n)-g(n-1)=f(n).$$ This can be done by the method of indeterminate coefficients. E.g. for the triangular numbers,

$$(an^2+bn)-(a(n-1)^2+b(n-1))=n\iff a=b=\frac12.$$

This method generalizes to polynomials times an exponential, $f(k)a^k$, leading to the recurrence $$g(n)a^n-g(n-1)a^{n-1}=f(n)a^n$$ or $$g(n)-\frac1ag(n-1)=f(n).$$ The exponential can be complex, allowing additional $\sin$ and $\cos$ factors.

Rational functions $f$ are most of the time difficult and require the use of special functions such as zeta $\zeta$ or polygamma $\psi^{(n)}$, unless telescoping occurs.

---

As a general rule, products are untractable.