Questions tagged [summation]

Questions about evaluating summations, especially finite summations. For infinite series, please consider the (sequences-and-series) tag instead.

Filter by
Sorted by
Tagged with
21
votes
1answer
56k views

Is there a partial sum formula for the Harmonic Series? [duplicate]

There is a partial sum formula for $$\sum_{x=1}^n x^1 = \frac{n(n+1)}{2}$$ and even one when the exponent of $x$ is $0$: $$\sum_{x=1}^n x^0 = n$$ but I cannot find one for exponent $-1$: $$\sum_{x=1}^...
11
votes
8answers
5k views

Proving $\sum_{k=1}^n k k!=(n+1)!-1$

Prove: $\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$ (preferably combinatorially) It's pretty easy to think of a story for the RHS: arrange $n+1$ people in a row and remove the the option of everyone ...
1
vote
4answers
22k views

proof by induction: sum of binomial coefficients $\sum_{k=0}^n (^n_k) = 2^n$ [duplicate]

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove $$\...
8
votes
1answer
287 views

Finite Series - reciprocals of sines

Find the sum of the finite series $$\sum _{k=1}^{k=89} \frac{1}{\sin(k^{\circ})\sin((k+1)^{\circ})}$$ This problem was asked in a test in my school. The answer seems to be $\dfrac{\cos1^{\circ}}{\sin^...
4
votes
1answer
889 views

Legendre symbol: Showing that $\sum_{m=0}^{p-1} \left(\frac{am+b}{p}\right)=0$

I have a question about Legendre symbol. Let $a$, $b$ be integers. Let $p$ be a prime not dividing $a$. Show that the Legendre symbol verifies: $$\sum_{m=0}^{p-1} \left(\frac{am+b}{p}\right)=0.$$ I ...
2
votes
5answers
675 views

How to derive $\sum_{n=0}^\infty 1 = -\frac{1}{2}$ without zeta regularization

On Wikipedia we find $\displaystyle \bbox[5px,border:1px solid #F5A029]{1 + 1 + 1+\dots =\sum_{n=0}^\infty 1 = -\frac{1}{2}}$ using (the rather complicated) zeta-function regularization. I asking for ...
3
votes
5answers
10k views

Proving the summation formula using induction: $\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$

I am trying to prove the summation formula using induction: $$\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$$ So far I have... Base case: Let n=1 and test $\frac{1}{k(k+1)} = 1-\frac{1}{n+1}$ $...
3
votes
3answers
334 views

How do we get the result of the summation $\sum\limits_{k=1}^n k \cdot 2^k$? [duplicate]

Possible Duplicate: Formula for calculating $\sum_{n=0}^{m}nr^n$ Can someone explain step by step how to derive the following identity? $$\sum_{k=1}^{n} k \cdot 2^k = 2(n \cdot 2^n - 2^n + 1) $$
47
votes
4answers
2k views

Proving $\sum_{n=-\infty}^\infty e^{-\pi n^2} = \frac{\sqrt[4] \pi}{\Gamma\left(\frac 3 4\right)}$

Wikipedia informs me that $$S = \vartheta(0;i)=\sum_{n=-\infty}^\infty e^{-\pi n^2} = \frac{\sqrt[4] \pi}{\Gamma\left(\frac 3 4\right)}$$ I tried considering $f(x,n) = e^{-x n^2}$ so that its ...
25
votes
4answers
74k views

How to prove a formula for the sum of powers of $2$ by induction?

How do I prove this by induction? Prove that for every natural number n, $ 2^0 + 2^1 + ... + 2^n = 2^{n+1}-1$ Here is my attempt. Base Case: let $ n = 0$ Then, $2^{0+1} - 1 = 1$ Which is true. ...
20
votes
5answers
2k views

Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially

$$\text{Evaluate } \sum_{k=1}^n k^2 \text{ and } \sum_{k=1}^{n}k(k+1) \text{ combinatorially.}$$ For the first one, I was able to express $k^2$ in terms of the binomial coefficients by considering a ...
9
votes
2answers
1k views

Reference for a tangent squared sum identity

Can anyone help me find a formal reference for the following identity about the summation of squared tangent function: $$ \sum_{k=1}^m\tan^2\frac{k\pi}{2m+1} = 2m^2+m,\quad m\in\mathbb{N}^+. $$ I ...
12
votes
2answers
611 views

Sum of powers of Harmonic Numbers

This is a natural extension of the question Sum of Squares of Harmonic Numbers. I became interested in this question while studying the problem A closed form of $\sum_{n=1}^\infty\left[ H_n^2-\left(\...
7
votes
3answers
6k views

Proof of $\cos \theta+\cos 2\theta+\cos 3\theta+\cdots+\cos n\theta=\frac{\sin\frac12n\theta}{\sin\frac12\theta}\cos\frac12(n+1)\theta$

State the sum of the series $z+z^2+z^3+\cdots+z^n$, for $z\neq1$. By letting $z=\cos\theta+i\sin\theta$, show that $$\cos \theta+\cos 2\theta+\cos 3\theta+\cdots+\cos n\theta=\frac{\sin\...
12
votes
6answers
2k views

Proof of $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$?

How do I prove that $$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$ I saw this in a book discussing generating functions.
4
votes
2answers
1k views

Evaluate $\sum\limits_{k=0}^n \binom{n}{k}$ combinatorially

Please help me to evaluate combinatorially the following sum: $$\sum_{k=0}^n \binom{n}{k}$$ Thank you.
9
votes
3answers
3k views

Proving that $\sum\limits_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$ [duplicate]

I have to prove that: $$\sum_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$$ I tried to open up the right side with Pascal's definition that: $$ { n \choose k} = {n-1 \choose {k}} + {n-1 \...
8
votes
2answers
2k views

How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $?

This sum is difficult. How can I compute it, without using calculus? $$\sum_{k = 1}^n \frac1{k + 1}\binom{n}{k}$$ If someone can explain some technique to do it, I'd appreciate it. Or advice ...
4
votes
2answers
1k views

Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$ [duplicate]

I'm looking for a proof of this identity but where j=m not j=0 http://www.proofwiki.org/wiki/Sum_of_Binomial_Coefficients_over_Upper_Index $$\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$$
4
votes
4answers
11k views

Proving the sum of the first $n$ natural numbers by induction [duplicate]

I am currently studying proving by induction but I am faced with a problem. I need to solve by induction the following question. $$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$ for all $n > 1$. Any ...
2
votes
3answers
159 views

Find the value of $\sum_0^n \binom{n}{k} (-1)^k \frac{1}{k+1}$ [duplicate]

Find the value of $\sum_0^n \binom{n}{k} (-1)^k \frac{1}{k+1}$. Writing out several terms, I think the answer is $1/(n+1)$, but I'm struggling to prove this. I would greatly appreciate it if someone ...
5
votes
4answers
1k views

Proving a special case of the binomial theorem: $\sum^{k}_{m=0}\binom{k}{m} = 2^k$ [duplicate]

I want to know if I can get some help with this proof. I tried, but I just cannot seem to get $2^{k}$. It states that, For $k \in \mathbb{Z}_{\ge 0}$, $$\sum^{k}_{m=0}\binom{k}{m} = 2^k$$ Thank ...
3
votes
2answers
283 views

$\sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} =\binom{m+n+1}{r+s+1}$ using Counting argument

I saw this question here:- Combinatorial sum identity for a choose function This looks so much like a vandermonde identity, I know we can give a counting argument for Vandermonde. However much I try ...
3
votes
0answers
2k views

$ 1^k+2^k+3^k+…+(p-1)^k $ always a multiple of $p$? [closed]

I would appreciate if somebody could help me with the following problem: Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is $$ 1^k+2^k+3^k+...+(p-1)^k $$ always a multiple of $p$ ?
50
votes
15answers
7k views

How can you prove that $1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$ without using induction?

Using mathematical induction, I have proved that $$1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$$ for every integer $n > 0$. I would like to know if there is another way of proving this result ...
26
votes
3answers
776 views

Closed form for $\sum_{n=1}^\infty\frac{(-1)^n n^4 H_n}{2^n}$

Please help me to find a closed form for the sum $$\sum_{n=1}^\infty\frac{(-1)^n n^4 H_n}{2^n},$$ where $H_n$ are harmonic numbers: $$H_n=\sum_{k=1}^n\frac{1}{k}=\frac{\Gamma'(n+1)}{n!}+\gamma.$$
28
votes
1answer
2k views

Sum of Squares of Harmonic Numbers

Let $H_n$ be the $n^{th}$ harmonic number, $$ H_n = \sum_{i=1}^{n} \frac{1}{i} $$ Question: Calculate the following $$\sum_{j=1}^{n} H_j^2.$$ I have attempted a generating function approach but ...
35
votes
7answers
3k views

Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$

Let $m,n\ge 0$ be two integers. Prove that $$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$ where $\delta_{mn}$ stands for the Kronecker's delta (defined by $\delta_{mn} = \begin{...
16
votes
4answers
7k views

Combinatorial interpretation of sum of squares, cubes

Consider the sum of the first $n$ integers: $$\sum_{i=1}^n\,i=\frac{n(n+1)}{2}=\binom{n+1}{2}$$ This has always made the following bit of combinatorial sense to me. Imagine the set $\{*,1,2,\ldots,n\}...
25
votes
3answers
748 views

How prove this sum $\sum_{n=1}^{\infty}\binom{2n}{n}\frac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}$

show that $$\sum_{n=1}^{\infty}\binom{2n}{n}\dfrac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}=5+4\sqrt{2}\left(\log{\dfrac{2\sqrt{2}}{1+\sqrt{2}}}-1\right)$$ where $H_{n}=1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{...
13
votes
6answers
815 views

Finding $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $

Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$ I got a hunch that it will depend on whether $n$ is a multiple of $6$ and equals to $\frac{2^n+2}{3}$ when $n$ is a ...
11
votes
3answers
3k views

Solve summation $\sum_{i=1}^n \lfloor e\cdot i \rfloor $

How to solve $$\sum_{i=1}^n \lfloor e\cdot i \rfloor $$ For a given $n$. For example, if $n=3$, then the answer is $15$, and it's doable by hand. But for larger $n$ (Such as $10^{1000}$) it gets ...
22
votes
5answers
679 views

Geometrical interpretation of $(\sum_{k=1}^n k)^2=\sum_{k=1}^n k^3$

Using induction it is straight forward to show $$\left(\sum_{k=1}^n k\right)^2=\sum_{k=1}^n k^3.$$ But is there also a geometrical interpretation that "proves" this fact? By just looking at those ...
16
votes
4answers
1k views

Where do summation formulas come from?

It's a classic problem in an introductory proof course to prove that $\sum_{ i \mathop =1}^ni = \frac{n(n+1)}{2}$ by induction. The problem with induction is that you can't prove what the sum is ...
22
votes
3answers
915 views

A (probably trivial) induction problem: $\sum_2^nk^{-2}\lt1$

So I'm a bit stuck on the following problem I'm attempting to solve. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling ...
13
votes
3answers
6k views

How do I evaluate this sum(involving the floor function)? [duplicate]

$$ \sum_{i=1}^N\left\lfloor\frac{N}{i}\right\rfloor $$ Is there a closed form expression to the above sum? (Mathematica doesn't give me anything)
8
votes
4answers
340 views

Summation of series $\sum_{n=1}^\infty \frac{n^a}{b^n}$?

How can we evaluate this series $$\sum_{n=1}^\infty \frac{n^a}{b^n}?$$ Here $a$ and $b$ are positive integers. If $b=1$ then series will be diverging, in other cases, it will be converging, but how ...
6
votes
3answers
525 views

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$; I was stuck with this question for a while... Help me please!!! Thanks!!!
4
votes
4answers
7k views

How does the sum of the series “$1 + 2 + 3 + 4 + 5 + 6\ldots$” to infinity = “$-1/12$”? [duplicate]

(I was requested to edit the question to explain why it is different that a proposed duplicate question. This seems counterproductive to do here, inside the question it self, but that is what I have ...
-1
votes
1answer
244 views

Estimating partial sums $\sum_{n = 1}^m \frac{1}{\sqrt{n}}$

Apostol's Calculus, exercise number I 4.7 13. Prove that if $n \geq 1$, then $$ 2(\sqrt{n+1} - \sqrt{n}) < \frac{1}{\sqrt{n}} < 2(\sqrt{n} - \sqrt{n-1}) $$ and use this to prove that if $...
3
votes
2answers
244 views

Prove $\sum_{i=1}^n i! \cdot i = (n+1)! - 1$?

Prove the summation: $$\sum_{i=1}^n i! \cdot i = (n+1)! - 1$$ using induction. base case: $n=1$: \begin{align*} \sum_{i=1}^1 i! \cdot i &= (1+1)! - 1 \\ 1 &= 2 - 1 \\ 1 &= 1 \end{align*...
4
votes
2answers
218 views

$\sum_{i=1}^n i\cdot i! = (n+1)!-1$ By Induction

I am trying to prove the following by Mathematical Induction: $$\sum_{i=1}^n i\cdot i! = (n+1)!-1\quad\text{for all integers $n\ge 1$}$$ My proof by Induction follows: First prove $P(1)$ is true, $...
1
vote
2answers
538 views

Simple binomial theorem proof: $\sum_{j=0}^{k} \binom{a+j}j = \binom{a+k+1}k$

I am trying to prove this binomial statement: For $a \in \mathbb{C}$ and $k \in \mathbb{N_0}$, $\sum_{j=0}^{k} {a+j \choose j} = {a+k+1 \choose k}.$ I am stuck where and how to start. My steps ...
43
votes
4answers
3k views

Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$

Let $\varphi(n)$ be Euler's totient function, the number of positive integers less than or equal to $n$ and relatively prime to $n$. Challenge: Prove $$\sum_{k=1}^n \left\lfloor \frac{n}{k} \right\...
30
votes
5answers
9k views

What is $\sum\limits_{i=1}^n \sqrt i\ $?

What is $\sum\limits_{i=1}^n\sqrt i\ $? Also I noticed that $\sum\limits_{i=1}^ni^k=P(n)$ where $k$ is a natural number and $P$ is a polynomial of degree $k+1$. Does that also hold for any real ...
13
votes
5answers
2k views

Find a formula for $\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$

I need to find a clear formula (without summation) for the following sum: $$\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$$ Well, the first few elements look like this: $1,1,1,2,2,2,2,2,3,3,3,...$ ...
6
votes
5answers
423 views

Infinite Series $1+\frac12-\frac23+\frac14+\frac15-\frac26+\cdots$

Was given the following infinite sum in class as a question, while we were talking about Taylor series expansions of $\ln(1+x)$ and $\arctan(x)$: $$1+\frac12-\frac23+\frac14+\frac15-\frac26+\cdots$$ ...
15
votes
13answers
5k views

How to explain the formula for the sum of a geometric series without calculus?

How to explain to a middle-school student the notion of a geometric series without any calculus (i.e. limits)? For example I want to convince my student that $$1 + \frac{1}{4} + \frac{1}{4^2} + \...
8
votes
3answers
718 views

Summing the series $(-1)^k \frac{(2k)!!}{(2k+1)!!} a^{2k+1}$

How does one sum the series $$ S = a -\frac{2}{3}a^{3} + \frac{2 \cdot 4}{3 \cdot 5} a^{5} - \frac{ 2 \cdot 4 \cdot 6}{ 3 \cdot 5 \cdot 7}a^{7} + \cdots $$ This was asked to me by a high school ...
10
votes
2answers
450 views

Show that $\sum\limits_{k=1}^\infty \frac{1}{k(k+1)(k+2)\cdots (k+p)}=\frac{1}{p!p} $ for every positive integer $p$

I have to prove that $$\sum_{k=1}^\infty \frac{1}{k(k+1)(k+2)\cdots (k+p)}=\dfrac{1}{p!p}$$ How can I do that?