How to guess a formula

Question

"The 'proof by induction' works well provided that we think we know the formula in advance. In other words, it is a good technique to transform a Conjecture in a Theorem." Biggs, N. L., Discrete Mathematics, ch. 4.4.

Sometime, creating the proper Conjecture is on our shoulder. But, what is the criteria? What elements should I keep considered in order to develop a formula?

E.g. Guess a formula for the sum

$\sum_{r = 1}^n(br + c),$

where b and c are given numbers, and prove it by using the principle of induction.

First, I tried to make a table:

$n:\qquad 1\qquad\qquad 2\qquad\qquad 3\qquad\qquad 4\qquad\qquad 5 $

$S_n:\quad 1b+c\quad 3b + 2c\quad 6b + 3c\quad10b + 4c\quad 15b + 5c $

but I failed to transform this pattern in an usable formula. The solution reports $\frac{1}{2}bn^2 + (\frac{1}{2}b + c)n$.

Which steps should I follow to get from the table I created to the correct formula? Apart from this specific case I reported as an example, is there a general method? Are there criteria? Guides? Is it mainly based on intuition and personal creativity and knowledge?

Answer 1

First observation: the general term $br+c$ is linear and you can work the terms separately and factor out the constants.

Second observation: the term $c$ is constant and just adds proportionally to $n$.

Third observation: the term $r$ grows linearly so you should expect its sum to grow superlinearly. Actually quadratically, because if the sum was $r^2$, the general term would be the difference $r^2-(r-1)^2=2r-1$, which is linear. This is a general property: for a general term that is a polynomial of degree $d$, the sum is a polynomial of degree $d+1$.

Then, you can postulate

$$S_n=pn^2+qn+s$$ and work by induction to obtain the undeterminate coefficients.

The general approach here is to guess the shape of the answer (inspired by known patterns in finite differences, derivatives and integrals) and adjust for details (by the method of unknown coefficients).

---

In this particular case, there is a shortcut: as the general term is linear, the average of the terms is also the average of the extreme terms. Hence the sum is the number of terms times the average of the extreme,

$$S_n=n\frac{b+c+bn+c}2.$$

Answer 2

$$\sum_{r = 1}^n(br + c) = \sum_{r = 1}^n(br)+\sum_{r = 1}^n(c)$$ $\sum_{r = 1}^n(br) =b\sum_{r = 1}^n(r) = b\left(\frac{1}{2}n(n+1)\right)$

$\sum_{r = 1}^n(c)=c\sum_{r = 1}^n(1)=c\:n$

$$\sum_{r = 1}^n(br + c) =\frac{b}{2}n(n+1)+c\:n$$

Answer 3

Let us try to come up with a formula for the following sum:

$$\sum_{i=1}^{n}\left[a_0+a_1i+\cdots a_ki^k\right]=a_0\sum_{i=1}^{n}i^0+a_1\sum_{i=1}^{n}i^1+\cdots+a_k\sum_{i=1}^{n}i^k.$$

As you can see this boils down to finding the power sums $S_k(n)=\sum_{i=1}^ni^k$. $S_0$ is obviously equal to $n$ as we are summing $1$ exactly $n$ times.

For the other terms, you need to know that $S_k(n)=\sum_{i=1}^ni^k$ is always expressible as a polynomial in $n$ of degree $k+1$. This claim can be intuitively understood if you estimate the sum by $S_k(n)=\sum_{i=1}^{n}i^k\leq \sum_{i=1}^{n}n^k=n\cdot n^k=n^{k+1}$, hence the polynomial cannot be of an higher degree than $k+1$.

So we assume that:

$$S_k(n)=b_0+b_1n+\cdots b_{k+1}n^{k+1}.$$

It seems difficult to guess the coefficients of this polynomial but noting that we have $k+2$ coefficients and being able to calculate $k+2$ values of $S_k(n)$ gives us a system of $k+2$ linear equations

$$S_k(0)=b_0+b_1\cdot 0+\cdots+b_{k+1}\cdot 0^{k+1}$$ $$S_k(1)=b_0+b_1\cdot 1+\cdots+b_{k+1}\cdot 1^{k+1}$$ $$\vdots$$ $$S_k(k+1)=b_0+b_1\cdot (k+1)+\cdots+b_{k+1}\cdot (k+1)^{k+1}$$

that can be easily solved for the coefficients by using Gaussian elimination.

After having obtained the coefficients of $b_j$ we can apply induction to prove that the formula is valid.