I want to find a candidate for this recurrence relation:
$$ P(n) = \left\{\begin{aligned} &1 &&: n = 0\\ &P(n-1)+n^2 &&: n>0 \end{aligned} \right.$$
Starting from 0 the first 8 values are 1,2,6,15,31,56,92,141.
I can't figure out a formula for this.
Asked
Active
Viewed 1,182 times
2
-
2Hint: try writing out what $P(1)$, $P(2)$, $P(3)$ are in terms of lower $P$'s using your recurrence. For example $P(1) = P(0) + 1^2$, $P(2) = P(1) + 2^2 = P(0) + 1^2 + 2^2$ etc – Alexander Vlasev Oct 09 '13 at 08:18
-
2the list should be $1,2,6,15,31,56,92,\color{red}{141}$. – achille hui Oct 09 '13 at 08:27
2 Answers
4
The first few values are 1,2,6,15,31....
The General Term is$${n*(n+1)*(2n+1)\over6}+1$$
Which is the Sum of Squares of first $n$ natural numbers + 1.
rnjai
- 1,774
0
Write $P(n) - P(n-1) = n^2 = 2{n \choose 2} + {n\choose 1}$. But ${n \choose 2} = {{n+1} \choose 3}-{n \choose 3}$, and ${n\choose 1} = {{n+1} \choose 2} - {n\choose 2}$, so we have $P(n) - P(n-1) = Q(n) - Q(n-1)$, where $Q(n) = 2{{n+1} \choose 3} + {{n+1} \choose 2} $. Since $P(0) = 1$ and $Q(0) = 0$, we can now conclude that $P(n) = Q(n) +1 = 2{{n+1} \choose 3} + {{n+1} \choose 2} + 1$.
Unfortunately, there is not a very nice closed form for this. But here's the best I can do (the first term here is the sum of the first $n$ squares, a fairly well-known quantity): $\frac{(n-\frac{1}{2})\cdot n\cdot (n+\frac{1}{2})}{3} + 1$
Andrew Dudzik
- 30,074
-
-
Niceness is relative. Every sum of the form $\sum_{m=0}^n m^k$, for $k$ a nonnegative integer, can be expressed as a degree $k+1$ polynomial. But the polynomials you get out are way more complicated than the polynomials you put in, so it's often more trouble than it's worth to simplify sums like that for $k$ bigger than $1$.
By comparison, $\sum_{m=0}^n {m \choose k}$ has a truly nice closed form, ${{n+1} \choose {k+1}}$, which is why you actually see it used in proofs from time to time.
– Andrew Dudzik Oct 09 '13 at 09:29 -
The polynomials you get are only complicated in comparison to the polynomials you are summing. The sums have a variable number of terms, while the resulting polynomials have a fixed number of terms and are quite suitable for computation. Besides, your ideal answer $\binom{n+1}{k+1}$ still takes $k+1$ multiplies and divides to evaluate, which is about the same as a polynomial of degree $k$. – marty cohen Oct 09 '13 at 21:47
-
@martycohen Are you making some point, or just trying to be argumentative? Yes, of course there are various reasons why, in principle, a polynomial closed form might be more useful than the sigma notation, and I'm sure there are lots of contrived examples to illustrate this. But as far as practical human understanding goes, we care a lot more about these operations when applied to bases they behave well on; it is no more worthwhile to write down $\sum_{m=0}^n m^10$ as a polynomial than it is to write down $\int_0^x {y\choose 10} dy$ as one. Heaven forbid that I do not find the latter nice. – Andrew Dudzik Oct 10 '13 at 02:39