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
193 votes
8 answers
98k views

How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression?

How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression? For example here is the sum of $\cos$ series: $$\sum_{k=0}^{n-1}\cos (a+k \cdot d) =\frac{\sin(n \times \frac{...
Quixotic's user avatar
  • 22.4k
76 votes
20 answers
23k views

Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$

After reading this question, the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1},$$ or, what is equivalent, $$\sum_{t=k}^n \binom{t}{k} = \binom{n+1}{k+1}.$$ What's ...
hlapointe's user avatar
  • 1,610
135 votes
7 answers
100k views

Values of $\sum_{n=0}^\infty x^n$ and $\sum_{n=0}^N x^n$

Why does the following hold: \begin{equation*} \displaystyle \sum\limits_{n=0}^{\infty} 0.7^n=\frac{1}{1-0.7} = 10/3\quad ? \end{equation*} Can we generalize the above to $\displaystyle \sum_{n=...
68 votes
16 answers
53k views

Proving $1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ using induction

How can I prove that $$1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$ for all $n \in \mathbb{N}$? I am looking for a proof using mathematical induction. Thanks
141 votes
36 answers
306k views

Proof that $1+2+3+4+\cdots+n = \frac{n\times(n+1)}2$

Why is $1+2+3+4+\ldots+n = \dfrac{n\times(n+1)}2$ $\space$ ?
b1_'s user avatar
  • 1,585
152 votes
33 answers
86k views

Sum of First $n$ Squares Equals $\frac{n(n+1)(2n+1)}{6}$

I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals: $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$ I really ...
Nathan Osman's user avatar
  • 1,873
17 votes
1 answer
10k views

$\sum \cos$ when angles are in arithmetic progression [duplicate]

Possible Duplicate: How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression? Prove $$\cos(\alpha) + \cos(\alpha + \beta) + \cos(\alpha + 2\beta) + \dots + \cos[\...
EvanChio's user avatar
  • 179
188 votes
28 answers
20k views

Proving the identity $\sum_{k=1}^n {k^3} = \big(\sum_{k=1}^n k\big)^2$ without induction

I recently proved that $$\sum_{k=1}^n k^3 = \left(\sum_{k=1}^n k \right)^2$$ using mathematical induction. I'm interested if there's an intuitive explanation, or even a combinatorial interpretation ...
Fernando Martin's user avatar
89 votes
9 answers
103k views

Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$

I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$. I already know the logical Proof: $${n \choose k}^2 = {...
Lance C's user avatar
  • 891
99 votes
4 answers
12k views

Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$

It's not difficult to show that $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$ On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
Skatche's user avatar
  • 1,512
18 votes
10 answers
17k views

How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$?

I am trying to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$ but am not able to think something except induction,which is of-course not necessary (I think) here, so I am ...
Quixotic's user avatar
  • 22.4k
17 votes
4 answers
12k views

Formula for calculating $\sum_{n=0}^{m}nr^n$

I want to know the general formula for $\sum_{n=0}^{m}nr^n$ for some constant $r$ and how it is derived. For example, when $r = 2$, the formula is given by:$$\sum_{n=0}^{m}n2^n = 2(m2^m - 2^m +1),$$...
hollow7's user avatar
  • 2,455
211 votes
5 answers
44k views

The sum of an uncountable number of positive numbers

Claim: If $(x_\alpha)_{\alpha\in A}$ is a collection of real numbers $x_\alpha\in [0,\infty]$ such that $\sum_{\alpha\in A}x_\alpha<\infty$, then $x_\alpha=0$ for all but at most countably many $\...
Benji's user avatar
  • 5,860
11 votes
9 answers
5k views

How to compute the formula $\sum \limits_{r=1}^d r \cdot 2^r$?

Given $$1\cdot 2^1 + 2\cdot 2^2 + 3\cdot 2^3 + 4\cdot 2^4 + \cdots + d \cdot 2^d = \sum_{r=1}^d r \cdot 2^r,$$ how can we infer to the following solution? $$2 (d-1) \cdot 2^d + 2. $$ Thank you
q0987's user avatar
  • 223
15 votes
4 answers
6k views

Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity) [duplicate]

Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
A_for_ Abacus's user avatar
10 votes
7 answers
23k views

How to prove Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$?

How can we prove that $$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$ (Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross.
Roiner Segura Cubero's user avatar
13 votes
7 answers
10k views

Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$ [duplicate]

Let $n$ be a positive integer. Prove that \begin{align} \sum_{k=0}^n \left(-1\right)^k \binom{n}{k} = 0 . \end{align} I tried to solve it using induction, but that got me nowhere. I think the ...
FranckN's user avatar
  • 1,294
38 votes
12 answers
86k views

Why $\sum_{k=1}^{\infty} \frac{k}{2^k} = 2$? [duplicate]

Can you please explain why $$ \sum_{k=1}^{\infty} \dfrac{k}{2^k} = \dfrac{1}{2} +\dfrac{ 2}{4} + \dfrac{3}{8}+ \dfrac{4}{16} +\dfrac{5}{32} + \dots = 2 $$ I know $1 + 2 + 3 + ... + n = \dfrac{n(n+1)}{...
jeebee's user avatar
  • 423
20 votes
5 answers
18k views

How to show that this binomial sum satisfies the Fibonacci relation?

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation. I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any hints ...
Kou's user avatar
  • 956
26 votes
4 answers
146k views

Proving by induction that $ \sum_{k=0}^n{n \choose k} = 2^n$

Prove by induction that for all $n \ge 0$: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ In the inductive step, use Pascal’s identity, which is: $${n+1 \choose k} = {n \choose k-1} ...
xyz's user avatar
  • 381
24 votes
5 answers
10k views

Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
JSchlather's user avatar
  • 15.4k
16 votes
6 answers
4k views

Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

The successive difference of powers of integers leads to factorial of that power. Here's the formula: $$\sum_{r=0}^{n}\binom{n}{r}(-1)^r(n-r)^n=n!$$ Can anyone give a proof of this result? Note: ...
hanugm's user avatar
  • 2,343
9 votes
5 answers
3k views

What is the formula for $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\cdots +\frac{1}{n(n+1)}$

How can I find the formula for the following equation? $$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\cdots +\frac{1}{n(n+1)}$$ More importantly, how would you approach finding the ...
Charles's user avatar
  • 315
35 votes
3 answers
4k views

Trig sum: $\tan ^21^\circ+\tan ^22^\circ+\cdots+\tan^2 89^\circ = \text{?}$

As the title suggests, I'm trying to find the sum $$\tan^21^\circ+\tan^2 2^\circ+\cdots+\tan^2 89^\circ$$ I'm looking for a solution that doesn't involve complex numbers, or any other advanced branch ...
Ninja Boy's user avatar
  • 3,103
17 votes
6 answers
11k views

Proving $\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$ with induction

I am just starting out learning mathematical induction and I got this homework question to prove with induction but I am not managing. $$\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$$ ...
Jason's user avatar
  • 2,367
10 votes
6 answers
895 views

Proving Binomial Identity without calculus

How to establish the following identities without the help of calculus: For positive integer $n, $ $$\sum_{1\le r\le n}\frac{(-1)^{r-1}\binom nr}r=\sum_{1\le r\le n}\frac1r $$ and $$\sum_{0\le r\le ...
lab bhattacharjee's user avatar
12 votes
2 answers
13k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
Bartek's user avatar
  • 6,235
39 votes
14 answers
8k views

Methods to compute $\sum_{k=1}^nk^p$ without Faulhaber's formula

As far as every question I've seen concerning "what is $\sum_{k=1}^nk^p$" is always answered with "Faulhaber's formula" and that is just about the only answer. In an attempt to make more interesting ...
Simply Beautiful Art's user avatar
23 votes
8 answers
53k views

Proving $\sum_{k=0}^n(-1)^k\binom nk=0$

Show that $$\sum_{k=0}^n(-1)^k\binom nk=0$$ So for odd $n$ we have an even number of terms. So $\binom nk=\binom n{n-k}$ which have opposite signs. Thus the sum is 0. For even $n$ we have that $$\...
Thomas's user avatar
  • 423
25 votes
3 answers
6k views

Does uncountable summation, with a finite sum, ever occur in mathematics?

Obviously, “most” of the terms must cancel out with opposite algebraic sign. You can contrive examples such as the sum of the members of R being 0, but does an uncountable sum, with a finite sum, ...
Mike Jones's user avatar
  • 4,450
41 votes
5 answers
20k views

How to find the sum of the series $1+\frac{1}{2}+ \frac{1}{3}+\frac{1}{4}+\dots+\frac{1}{n}$?

How to find the sum of the following series? $$1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{n}$$ This is a harmonic progression. So, is the following formula correct? $\frac{(number ~...
Sachin's user avatar
  • 9,756
38 votes
4 answers
3k views

A closed form of $\sum_{k=1}^\infty\frac{(-1)^{k+1}}{k!}\Gamma^2\left(\frac{k}{2}\right)$

I am looking for a closed form of the following series \begin{equation} \mathcal{I}=\sum_{k=1}^\infty\frac{(-1)^{k+1}}{k!}\Gamma^2\left(\frac{k}{2}\right) \end{equation} I have no idea how to ...
Anastasiya-Romanova 秀's user avatar
11 votes
3 answers
3k views

How do you calculate this limit $\lim_{n\to\infty}\sum_{k=1}^{n} \frac{k}{n^2+k^2}$?

How to find the value of $\lim_{n\to\infty}S(n)$, where $S(n)$ is given by $$S(n)=\displaystyle\sum_{k=1}^{n} \dfrac{k}{n^2+k^2}$$ Wolfram alpha is unable to calculate it. This is a question from a ...
user1001001's user avatar
  • 5,143
75 votes
4 answers
114k views

$\sum k! = 1! +2! +3! + \cdots + n!$ ,is there a generic formula for this?

I came across a question where I needed to find the sum of the factorials of the first $n$ numbers. So I was wondering if there is any generic formula for this? Like there is a generic formula for the ...
vikiiii's user avatar
  • 2,681
45 votes
8 answers
8k views

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$? I know this is well-known. But how to prove it rigorously? Even mathematical induction does not seem so straight-forward. ...
Qiang Li's user avatar
  • 4,087
41 votes
2 answers
202k views

How to get to the formula for the sum of squares of first n numbers? [duplicate]

Possible Duplicate: How do I come up with a function to count a pyramid of apples? Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$? Finite Sum of Power? I know that the sum of ...
Straightfw's user avatar
  • 1,558
36 votes
5 answers
9k views

use of $\sum $ for uncountable indexing set

I was wondering whether it makes sense to use the $\sum $ notation for uncountable indexing sets. For example it seems to me it would not make sense to say $$ \sum_{a \in A} a \quad \text{where A is ...
Beltrame's user avatar
  • 3,076
31 votes
5 answers
2k views

How to prove $\sum\limits_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$?

Other than the general inductive method,how could we show that $$\sum_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$$ Apart from induction, I tried with Wolfram Alpha to check the validity, ...
Quixotic's user avatar
  • 22.4k
21 votes
7 answers
18k views

Proving $\sum_{k=0}^{n}\cos kx=\frac{1}{2}+\frac{\sin(n+\frac12)x}{2\sin\frac x2}$

I am being asked to prove that $$\sum\limits_{k=0}^{n}\cos(kx)=\frac{1}{2}+\frac{\sin(\frac{2n+1}{2}x)}{2\sin(x/2)}$$ I have some progress made, but I am stuck and could use some help. What I did: It ...
Belgi's user avatar
  • 23.1k
12 votes
3 answers
5k views

Proof of a combinatorial identity: $\sum\limits_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$ [duplicate]

Possible Duplicate: Identity involving binomial coefficients This was part of a homework assignment that I had, and I couldn't figure it out. Now it is bugging me. Can anyone help me? Although a ...
Kyle d'Oliveira's user avatar
10 votes
4 answers
2k views

Evaluating Combination Sum $\sum{n+k\choose 2k} 2^{n-k}$

Evaluate $$\sum_{k=0}^n{n+k\choose 2k} 2^{n-k}$$ So im not really sure how to begin with this. I would imagine we start with dividing out $2^{n}$, but not really sure much past that
Mr.Meeseeks's user avatar
4 votes
2 answers
4k views

Proving the geometric sum formula by induction

$$\sum_{k=0}^nq^k = \frac{1-q^{n+1}}{1-q}$$ I want to prove this by induction. Here's what I have. $$\frac{1-q^{n+1}}{1-q} + q^{n+1} = \frac{1-q^{n+1}+q^{n+1}(1-q)}{1-q}$$ I wanted to factor a $q^{...
furashu's user avatar
  • 483
34 votes
8 answers
6k views

Is there a direct, elementary proof of $n = \sum_{k|n} \phi(k)$?

If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically ...
JessicaB's user avatar
  • 2,067
13 votes
8 answers
3k views

I found this odd relationship, $x^2 = \sum_\limits{k = 0}^{x-1} (2k + 1)$. [duplicate]

I stumbled across this relationship while I was messing around. What's the proof, and how do I understand it intuitively? It doesn't really make sense to me that the sum of odd numbers up to $2x + 1$ ...
undo_all's user avatar
  • 255
1 vote
8 answers
664 views

Prove that $\left(\sum^n_{k=1}x_k\right)\left(\sum^n_{k=1}y_k\right)\geq n^2$

If $x_1,...,x_n$ are positive real numbers and if $y_k=1/x_k$, prove that $$\left(\sum^n_{k=1}x_k\right)\left(\sum^n_{k=1}y_k\right)\geq n^2.$$ I've been learning induction, and I've come across this ...
Jackson's user avatar
  • 420
113 votes
5 answers
122k views

What is the term for a factorial type operation, but with summation instead of products?

(Pardon if this seems a bit beginner, this is my first post in math - trying to improve my knowledge while tackling Project Euler problems) I'm aware of Sigma notation, but is there a function/name ...
barfoon's user avatar
  • 1,349
32 votes
7 answers
14k views

Floor function properties: $[2x] = [x] + [ x + \frac12 ]$ and $[nx] = \sum_{k = 0}^{n - 1} [ x + \frac{k}{n} ] $

I'm doing some exercises on Apostol's calculus, on the floor function. Now, he doesn't give an explicit definition of $[x]$, so I'm going with this one: DEFINITION Given $x\in \Bbb R$, the integer ...
Pedro's user avatar
  • 122k
51 votes
9 answers
6k views

Finite Sum $\sum\limits_{k=1}^{m-1}\frac{1}{\sin^2\frac{k\pi}{m}}$

Question : Is the following true for any $m\in\mathbb N$? $$\begin{align}\sum_{k=1}^{m-1}\frac{1}{\sin^2\frac{k\pi}{m}}=\frac{m^2-1}{3}\qquad(\star)\end{align}$$ Motivation : I reached $(\star)$ by ...
mathlove's user avatar
  • 138k
14 votes
4 answers
29k views

Solve $\sum nx^n$

I am trying to find a closed form solution for $\sum_{n\ge0} nx^n\text{, where }\lvert x \rvert<1$. This solution makes sense to me: $\sum_{n\ge0} x^n=(1-x)^{-1} \\ \frac{d}{d x} \sum_{n\ge0} x^n ...
dbyrne's user avatar
  • 557
2 votes
5 answers
24k views

Proving $ 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ for all $n\geq 2$ by induction

Question: Let $P(n)$ be the statement that $1+\dfrac{1}{4}+\dfrac{1}{9}+\cdots +\dfrac{1}{n^2} <2- \dfrac{1}{n}$. Prove by mathematical induction. Use $P(2)$ for base case. Attempt at solution: ...
Donald Dang's user avatar

1
2 3 4 5
51