Finding the $S_n$ of a recursion

Question

$$\sum_{k=0}^{n} (1+2k+4(k(k+1)))=?$$

In order to find the $S_n$ what methods are best fitted for such problem? Is it possible to use the lemma $\sum_{i=0}^{n} i= {n(n+1)}/2$ and plug in? I tried but it did not work. So am i wrong or missing something? I feel i have to expand the expression and try to find common factors right? I'm really new to these concepts so please bare take it easy on me According an online sigma notation calculator this is true: $s(1)= 12, s(2) = 41, s(3)=96$

An explanation with the same problem will be helpful. Thanks.

Answer 1

Well, first I would separate the sum into parts: $$\sum_{k=0}^{n} (1+2k+4(k(k+1)))=\sum_{k=0}^{n}1 + \sum_{k=0}^{n}2k + \sum_{k=0}^{n}4(k(k+1)))$$ $$ (I) \sum_{k=0}^{n}1=(n+1)$$ $$(II)\sum_{k=0}^{n}2k=2\sum_{k=0}^{n}k=2\frac{(n+1)n}{2}=(n+1)n$$ $$(III) \sum_{k=0}^{n}4(k(k+1))=4\sum_{k=0}^{n}\left[k^2+k\right]=4\sum_{k=0}^{n}k^2+4\sum_{k=0}^{n}k$$ $$(IIIa) 4\sum_{k=0}^{n}k^2=4\frac{n(n+1)(2n+1)}{6}=\frac{2n(n+1)(2n+1)}{3}$$ $$(IIIb) 4\sum_{k=0}^{n}k=2n(n+1)$$ Summing it all up: $$S_n=(n+1)+(n+1)n+\frac{2n(n+1)(2n+1)}{3}+2n(n+1)$$ Which you can easily simplify

Answer 2

We may exploit the following identity: $$ \sum_{k=n}^{N}\binom{k}{n}=\binom{N+1}{n+1}.\tag{1}$$ We have: $$ \sum_{k=0}^{n}(2k+1) = (n+1)^2,\qquad \sum_{k=0}^{n}4k(k+1) = 8\sum_{k=0}^{n}\binom{k+1}{2} = 8\binom{n+2}{3}\tag{2} $$ hence: $$ \sum_{k=0}^{n}\left(2k+1+4k(k+1)\right) = (n+1)^2 + \frac{4(n+2)(n+1)n}{3} = \color{red}{\frac{(n+1)(4n^2+11n+3)}{3}}.\tag{3}$$

Answer 3

\begin{align} \sum_{k=0}^{n} (1+2k+4(k(k+1))) &= \sum_{k=0}^{n} (1+6k+4k^2) \\[2ex] &= \sum_{k=0}^{n} 1 + 6\sum_{k=0}^{n}k+4\sum_{k=0}^{n}k^2 \\[2ex] &= (n+1) + 6\frac{n(n+1)}{2}+4\frac{n(n+1)(2n+1)}{6} \\[2ex] \end{align}

In the last line I used the known partial sum formulas $$ \sum_{k=0}^{n}k=\frac{n(n+1)}{2} \quad \text{and} \quad \sum_{k=0}^{n}k^2=\frac{n(n+1)(2n+1)}{6}$$

Answer 4

This one succumbs very easily to the methods of finite calculus [PDF].

$$\begin{align*} \sum_{k=0}^n\big(1+2k+4k(k+1)\big)&=\sum_{k=0}^n1+\sum_{k=0}^n2k+4\sum_{k=0}^n(k+1)^{\underline2}\\ &=[k]_0^{n+1}+\left[k^{\underline2}\right]_0^{n+1}+\frac43\left[(k+1)^{\underline3}\right]_0^{n+1}\\ &=(n+1)+(n+1)n+\frac43(n+2)(n+1)n\\ &=(n+1)\left(1+n+\frac43n(n+2)\right)\\ &=\frac{(n+1)(3+3n+4n^2+8n)}3\\ &=\frac{(n+1)(3+11n+4n^2)}3\;. \end{align*}$$

Here $x^{\underline n}$ is the falling factorial, and we use the fact that

$$\sum_{k=a}^nk^{\underline m}=\left[\frac{k^{\underline{m+1}}}{m+1}\right]_a^{b+1}=\frac1{m+1}\left((b+1)^{\underline{m+1}}-a^{\underline{m+1}}\right)\;.$$