Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [summation]

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

0
votes
1answer
162 views

amortized analysis

a) define f(k) as the largest power of 2 that divides k. For example, f(25) = 1, f(42) = 2, f(144) = 16. What is ${1 \over k}\sum_1^k f(k)$? b) define f(k) as the square of largest power of 2 that ...
4
votes
4answers
147 views

Binomial series with two binomial coefficents

My question reads: Does this formula has mathematical meaning at first place? Is it summable? $$\sum^{\infty}_{k=0}{n\choose k}{m\choose k} x^k$$
6
votes
2answers
254 views

Sum of the Reciprocal of the Difference of Two Squares

Is there a closed-form expression for the sum: $$ \sum \limits_{i=2}^{n} \frac{1}{i^2-1} $$
1
vote
3answers
158 views

Working on this summation proof

$$\sum_{i=1}^n t^{i-1}$$ I am stuck with the proof of this equality.
3
votes
3answers
2k views

Prove by induction $\sum_{i=1}^ni^3=\frac{n^2(n+1)^2}{4}$ for $n\ge1$ [duplicate]

Prove the following statement $S(n)$ for $n\ge1$: $$\sum_{i=1}^ni^3=\frac{n^2(n+1)^2}{4}$$ To prove the basis, I substitute $1$ for $n$ in $S(n)$: $$\sum_{i=1}^11^3=1=\frac{1^2(2)^2}{4}$$ Great. ...
7
votes
3answers
325 views

Proving $\sum\limits_{i=1}^{n}{\frac{i}{2^i}}=2-\frac{n+2}{2^n}$ by induction.

Theorem (Principle of mathematical induction): Let $G\subseteq \mathbb{N}$, suppose that a. $1\in G$ b. if $n\in \mathbb{N}$ and $\{1,...,n\}\subseteq G$, then $n+1\in G$ ...
6
votes
2answers
5k views

Smallest eigenvalues of Sum of Two Positive Matrices

Let $C = A + B$, where $A$, $B$, and $C$ are positive definite matrices. In addition, $C$ is fixed. Let $\lambda (A)$, $\lambda (B)$, and $\lambda (C)$ be smallest eigenvalues of $A$, $B$, and $C$, ...
9
votes
5answers
387 views

How can I compute the sum of $ {m\over\gcd(m,n)}$?

$$ \sum_{m =1}^n {m\over\gcd(m,n)}$$ For example, for 1 it is $${1\over\gcd(1,1)} =1;$$ for 5 it is $${1\over \gcd(1,5)}+{2\over \gcd(2,5)}+{3\over \gcd(3,5)}+{4\over \gcd(4,5)}+{5\over \gcd(5,5)}=...
3
votes
4answers
5k views

modulo of series summation

I have trouble with computing modulo. First, I have a summation of series like this: $$1+3^2+3^4+\cdots+3^n$$ And this is the formula which can be used to compute the series: $$S=\frac{1-3^{n+2}}{1-3^...
0
votes
3answers
1k views

How to prove by induction that $\sum^n_{i=1}2^{i-1}=2^n-1$? [duplicate]

Possible Duplicate: How do I prove this by induction? (sum of powers of 2) Summation equation for $2^{x-1}$ How can I prove the following by induction? $$ \sum^n_{i=1}2^{i-1}=2^n-1 $$ I get to ...
0
votes
1answer
56 views

Complex analysis equality in a limited sum

Let $z=e^{i\theta}$ with $\theta \in [0,2\pi[$ . Consider the sum $$ \sum_{n=1}^{N} (e^{i\theta})^n. $$ How could this be equal to $$ \frac{1-e^{iN+T\theta}}{1-e^{i\theta}} \quad ? $$ I tried to ...
1
vote
2answers
219 views

Is it possible to make $\sum_{k=0}^{n-i}10^k \binom{n-i}{k}$ shorter?

I've got some expression $$\sum_{i=1}^n\left( 2^{i-1} a_i \sum_{k=0}^{n-i}10^k \binom{n-i}{k} \right)$$ $a_i$ stands for i-th digits in number. I came up with this formula from task in which we ...
2
votes
3answers
953 views

Prove the following identity without using induction: $\sum\limits_{i=0}^n a^i = \frac{1-a^{n+1}}{1-a}$ for $a\neq1$

I'm struggling with proving $$ \sum^n_{i=0}a^i = \frac{1-a^{n+1}}{1-a} $$ for $a\neq1$, not sure where to start.
1
vote
1answer
310 views

How can the Möbius function be applied to a series?

Given a series $p_n(s)=\sum_{k=1}^n a_k $. I'd like to get $\hat{p}_n(s)=\sum_{k=1}^n \mu(k)a_k $. Think of $a_k=k^{-s}$ for example. If you let $n$ go to $\infty$, you'll see the well-known relation ...
2
votes
2answers
242 views

Simplify $\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$

I am trying to simplify an expression involving summation as follows: $$\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$$ where $n$ is an integer, and $x$ is a positive real number. At a first glance,...
2
votes
1answer
166 views

Evaluate $\sum_{n=1}^{1024}\left \lfloor \log_2n \right \rfloor$.

Evaluate $\sum_{n=1}^{1024}\left \lfloor \log_2n \right \rfloor$. I thought the answer is $1+1*2+2*2^2+3*2^3+4*2^4+5*2^5+6*2^6+7*2^7+8*2^8+9*2^9+2^{10}=9219$, but the answer should be 8204. What ...
10
votes
0answers
174 views

Finding $\frac{3}{1!+2!+3!}+\frac{4}{2!+3!+4!} +\frac{5}{3!+4!+5!}+\cdots+\frac{2008}{2006!+2007!+2008!}$ [duplicate]

How to find : $$\frac{3}{1!+2!+3!}+\frac{4}{2!+3!+4!} +\frac{5}{3!+4!+5!}+\cdots+\frac{2008}{2006!+2007!+2008!}$$
3
votes
2answers
1k views

Combinatorially prove that $\sum_{i=0}^n {n \choose i} 2^i = 3^n $

So i'm not sure at all how to prove things using a combinatorial proof. Where to do i start? What do i need to think about etc. For example how would i prove $$\sum_{i=0}^n {n \choose i} 2^i = 3^n $$...
8
votes
2answers
425 views

Finding $\sum\limits_{n=1}^{9999} \frac{1}{(\sqrt{n+1}+\sqrt{n})(\sqrt[4]{n}+\sqrt[4]{n+1})} $

How we can find $$\sum_{n=1}^{9999} \frac{1}{(\sqrt{n+1}+\sqrt{n})(\sqrt[4]{n}+\sqrt[4]{n+1})} $$
24
votes
7answers
3k 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 ...
3
votes
2answers
286 views

Evaluate the following limit: $\lim_{n\to\infty}\left(\sum_{r=1}^{n}{\frac{r}{n^{2}+n+r}}\right)$

Evaluate the following limit: $$\lim_{n\to\infty}\left(\sum_{r=1}^{n}{\frac{r}{n^{2}+n+r}}\right)$$ The answer given is $\frac{1}{2}$.
3
votes
2answers
1k views

Evaluation of $ \sum_{k=0}^n \cos k\theta $

I just wanted to evaluate $$ \sum_{k=0}^n \cos k\theta $$ and I know that it should give $$ \cos\left(\frac{n\theta}{2}\right)\frac{\sin\left(\frac{(n+1)\theta}{2}\right)}{\sin(\theta / 2)} $$ ...
6
votes
4answers
219 views

Help evaluating a limit

I have the following limit: $$\lim_{n\rightarrow\infty}e^{-\alpha\sqrt{n}}\sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose k}\sum_{m=0}^{n-1-k}\frac{(\alpha\sqrt{n})^m}{m!}$$ where $\alpha>0$. ...
1
vote
2answers
1k views

Summation of series of product of Fibonacci numbers

What is the sum of following product of Fibonacci numbers $$\sum_{k=1}^{n-1} Fib(k)*Fib(n+3-k)$$ can anyone suggest only approach to find general term?
4
votes
2answers
15k views

Sigma notation only for odd iterations

$ \sum_{i=0}^{5}{i^2} = 0^2+1^2+2^2+3^2+4^2+5^2 = 55 $ How to write this Sigma notation only for odd numbers: $ 1^2+3^2+5^2 = 35 $ ?
2
votes
1answer
122 views

The number of ways to represent $(n^2+n)/4$ as a sum of $n/2$ distinct integers in $1,\dots,n$

For any positive integer $n$ (using integer division only), let $P(n)$ denote the number of ways in which the integer $(n^2+n)/4$ can be expressed as a sum of exactly $n /2$ distinct elements of the ...
4
votes
0answers
213 views

Simplifying the sum with binomial coefficients: $\sum\limits_{k=0}^n {2k\choose k}{2n-2k\choose n-k}$ [duplicate]

Possible Duplicate: Identity involving binomial coefficients Simplify the sum: $$\sum_{k=0}^n {2k\choose k}{2n-2k\choose n-k}$$ So we can denote $a_n=\sum\limits_{k=0}^n {2k\choose k}{2n-2k\...
20
votes
7answers
6k 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 ...
13
votes
3answers
10k views

How to prove Lagrange trigonometric identity [duplicate]

I would to prove that $$1+\cos \theta+\cos 2\theta+\ldots+\cos n\theta =\displaystyle\frac{1}{2}+ \frac{\sin\left[(2n+1)\frac{\theta}{2}\right]}{2\sin\left(\frac{\theta}{2}\right)}$$ given that $$1+...
25
votes
2answers
128k 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 ...
3
votes
3answers
202 views

Why does he need to first prove the sum of the $n$ integers and then proceed to prove the concept of arithmetical progression?

I'm reading What is Mathematics, on page 12 (arithmetic progression), he gives one example of mathematical induction while trying to prove the concept of arithmetic progression. There's something ...
6
votes
4answers
2k views

What is the sum of $\sum\limits_{i=1}^{n}ip^i$?

What is the sum of $\sum\limits_{i=1}^{n}ip^i$ and does it matter, for finite n, if $|p|>1$ or $|p|<1$ ? Edition : Why can I integrate take sum and then take the derivative ? I think that ...
1
vote
6answers
888 views

Summation equation for $2^{x-1}$

Since everyone freaked out, I made the variables are the same. $$ \sum_{x=1}^{n} 2^{x-1} $$ I've been trying to find this for a while. I tried the usually geometric equation (Here) but I couldn't get ...
5
votes
2answers
312 views

Finding the sum of series; sum of squares

Is there any way to find the sum of the below series ? $$\underbrace{10^2 + 14^2 + 18^2 +\cdots}_{41\text{ terms}}$$ I got asked this question in a competitive exam.
0
votes
5answers
3k views

Prove by induction: $2^n = C(n,0) + C(n,1) + \cdots + C(n,n)$ [duplicate]

This is a question I came across in an old midterm and I'm not sure how to do it. Any help is appreciated. $$2^n = C(n,0) + C(n,1) + \cdots + C(n,n).$$ Prove this statement is true for all $n \...
5
votes
4answers
2k views

Alternating sum of binomial coefficients

Calculate the sum: $$ \sum_{k=0}^n (-1)^k {n+1\choose k+1} $$ I don't know if I'm so tired or what, but I can't calculate this sum. The result is supposed to be $1$ but I always get something ...
6
votes
1answer
5k views

Show $1 + 2 \sum_{n=1}^N \cos n x = \frac{ \sin (N + 1/2) x }{\sin \frac{x}{2}}$ for $x \neq 0$ [duplicate]

For $x \neq 0$, $$ 1 + 2 \sum_{n=1}^N \cos n x = \frac{ \sin (N + 1/2) x }{\sin \frac{x}{2}} $$
2
votes
0answers
331 views

sum with permutations

Let $a$ be vector in $R^{2m}$. And let $S_{2m}$ be group of all permutations on the set $\{1,\dots,2m\}$. I would like to calculate $$ \sup_{\pi\in S_{2m}}\sum_{d(\sigma, \pi)=2}\left(\left|\sum_{k=...
22
votes
3answers
905 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 ...
3
votes
4answers
395 views

Computing a sum of binomial coefficients: $\sum_{i=0}^m \binom{N-i}{m-i}$

Does anyone know a better expression than the current one for this sum? $$ \sum_{i=0}^m \binom{N-i}{m-i}, \quad 0 \le m \le N. $$ It would help me compute a lot of things and make equations a lot ...
3
votes
2answers
3k views

Prove that for $n \in \mathbb{N}, \sum\limits_{k=1}^{n} (2k+1) = n^{2} + 2n $

I'm learning the basics of proof by induction and wanted to see if I took the right steps with the following proof: Theorem: for $n \in \mathbb{N}, \sum\limits_{k=1}^{n} (2k+1) = n^{2} + 2n $ ...
9
votes
3answers
1k views

Which number was removed from the first $n$ naturals?

A number is removed from the set of integers from $1$ to $n$. Now, the average of remaining numbers turns out to be $40.75$. Which integer was removed? By some brute force, I got $61$. I want to know ...
2
votes
1answer
132 views

Prove that $ \sqrt{\sum_{j=1}^{n}a_j^2} \le \sum_{j=1}^{n}|a_j|$, for all $a_i \in \mathbb{R}, i=\{1,2,…,n\}$

As the title says, prove that $ \sqrt{\sum_{j=1}^{n}a_j^2} \le \sum_{j=1}^{n}|a_j|$, for all $a_i \in \mathbb{R}, i=\{1,2,...,n\}$. I can solve for the case of n=2, but kind of stuck while proving the ...
7
votes
7answers
383 views

What is the result of sum $\sum\limits_{i=0}^n 2^i$ [duplicate]

Possible Duplicate: the sum of powers of $2$ between $2^0$ and $2^n$ What is the result of $$2^0 + 2^1 + 2^2 + \cdots + 2^{n-1} + 2^n\ ?$$ Is there a formula on this? and how to prove the ...
5
votes
2answers
4k views

Show that $\sum\nolimits_{d|n} \frac{1}{d} = \frac{\sigma (n)}{n}$ for every positive integer $n$.

Show that $\sum\nolimits_{d|n} \frac{1}{d} = \frac{\sigma (n)}{n}$ for every positive integer $n$. where $\sigma (n)$ is the sum of all the divisors of $n$ and $\sum\nolimits_{d|n} f(d)$ is the ...
24
votes
4answers
2k views

What are the applications of finite calculus

I'm reading through Concrete Mathematics [Graham, Knuth, Patashnik; 2nd edition], and in the section regarding Summation, they have a sub-section entitled "Finite and Infinite Calculus". In this ...
14
votes
2answers
4k views

Finite Sum of Power?

Can someone tell me how to get a closed form for $$\sum_{k=1}^n k^p$$ For $p = 1$, it's just the classic $\frac{n(n+1)}2$. What is it for $p > 1$?
10
votes
2answers
41k views

Interpreting formulas with $\Sigma \Sigma$ (two sigma)

Could you please tell me what I am supposed to do when facing two sigma ($\Sigma \Sigma$), such as in the covariance formula? Should I sum the results obtained by each or rather multiply them?
8
votes
2answers
28k views

Sum of $\cos(k x)$ [duplicate]

I'm trying to calculate the trigonometric sum : $$\sum\limits_{k=1}^{n}\cos(k x)$$ This is what I've tried so far : $$\renewcommand\Re{\operatorname{Re}} \begin{align*} \sum\limits_{k=1}^{n}\cos(k x) ...
4
votes
2answers
1k views

How to show $\sum_{n=0}^m \frac{1}{n+1}\binom{m}{n} = \frac{2^m-1}{m+1}$

This is the homework, and it shouldn't be difficult, but I can't find the proper identity that would help me simplify this sum: $$\sum_{n=0}^m \frac{1}{n+1}\binom{m}{n}$$ Through calculating the ...