0
votes
0answers
39 views

The sum of palindromes from 100 to 900

I'm working with palindromes from $100-999$. I'm having trouble with the step highlighted in red. Can someone explain the algebra to me? Taken from: Discrete and Combinatorial Mathematics: An ...
0
votes
1answer
52 views

Sumatory formula

Anybody knows the formula for this, because I don't know how to write it from the basic formula of $$\frac{n(n+1)}{2}$$: $$\sum _{i=1}^{n}{ \sum _{j=1}^{ n}{ \sum _{ k=1 }^{ n }{ \sum _{ h=1 }^{ n ...
0
votes
1answer
98 views

Big Mathematics Challenge on Set and Summation? [closed]

please be aware that this is not homework. it's past PHD entrance Exam on 2011. Suppose: $$B=\{(A_1,A_2,A_3) \mid \forall i; 1\le i \le 3; A_i \subseteq \{1,\ldots,20\}\}$$ if we have: ...
0
votes
3answers
43 views

How do I finish this summations problem?

I have posted a picture since I don't know how to make the summation symbols with the lower and upper summations on keyboard, sorry about that.. $$\sum_{a=1}^9\sum_{b=0}^9(101a+10b)$$ The answer is ...
1
vote
1answer
26 views

Discrete math: Sum of Geometric series on a problem - Notes make little sense.

I've been reading a PDF of slides from my Discrete Math I professor. The title is Sums, Products and Asymptotic Estimations. He gives us a problem to fire off the lecture, which is the following: ...
1
vote
1answer
24 views

Prove summation related to cycles

Let $b_r(n,k)$ be the number of n-permutations with $k$ cycles, in which numbers $1,2,\dots,r$ are in one cycle. Prove that for $n \geq r $ there is: $$ \sum_{k=1}^{n} ...
0
votes
0answers
39 views

Prove that maximum 9 trailing zeroes in this summation

I am trying to prove that there are a maximum of 9 trailing $0$'s at the end of this summation: $$\sum_{k=1}^{k=m} k^n$$ for $1\le n\le 1000000$ and $m\le 100$. Any help on how to approach?
0
votes
2answers
125 views

Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)] $ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
2
votes
3answers
97 views

Summation with Ceilinged Logarithmic Function

According to Johann Blieberger's paper - "Discrete Loops and Worst Case Performance" (1994): $$ \sum_{i = 1}^{n}\left \lceil \log_2{(i)} \right \rceil = n\left \lceil \log_2{(n)} \right \rceil - ...
0
votes
3answers
56 views

How can I calculate summations of modulus expressions?

I know that the following holds true: $$\sum_{k=1}^n k = {n (n + 1) \over 2} $$ Can modulus expressions be simplified in similar ways? For example: $$\sum_{k=1}^n (k\bmod x) = ?? $$ To be clear, ...
1
vote
1answer
31 views

Summation with absolute value

How can I solve $\sum_{k=-2}^{\infty}(\frac{1}{2})^{k}\alpha^{|n-k|}$ for every whole number n? Note that $-1<\alpha<1$ Thank you
1
vote
2answers
79 views

Use the recursive definition of summation together with mathematical induction to prove a sequence

Use the recursive definition of summation together with mathematical induction to prove that for all positive integers $n$ if $a_1, a_2,\ldots, a_n$ are real numbers, then $$\sum_{k=1}^n(3a_k - 2k + ...
0
votes
1answer
19 views

Proving claims about sequences by induction?

I am learning how to prove claims about finite sequences right now. Can you help me prove or disprove the following claim? ...
0
votes
1answer
18 views

Need to get summation formula?

I have: $$ Y[k]= \frac 1N \sum_{n=0}^{N-1} exp^{j2\pi\epsilon n/N} $$ After simplification, I have to get: $$ Y[k]= \frac {\sin \pi\epsilon} {N\sin(\pi\epsilon/N)} \cdot ...
0
votes
2answers
31 views

how do I figure out Which of the following is true?

I am studying for my exam and I am kind of stuck on this question, how is it that the answer is a)? can someone explain this please. Which one of the following is true? a) $$\sum_{k=0}^{n} ...
2
votes
4answers
66 views

Proving for all n that $\sum_{i=0}^n \frac1{2^{i}} < 2$

Proving for all n $\in \mathbb N$, $$\sum_{i=0}^n \frac1{2^{i}} < 2$$ Hint. First prove that the left hand side can be expressed in closed form, i.e. without using the summation operator. This is ...
0
votes
0answers
9 views

Proving a disequality involving hypergeometric distribution

How would you prove symbolically the following property? $$H(m_a+1,p_a+1,m,p) < H(m_a,p_a,m,p)$$ where $H(m_a,p_a,m,p)$ is the probability of drawing $m_a$ white balls in a series of $m$ ...
0
votes
0answers
25 views

Simplify the following summation involving the Floor function

Let $x,y,n \in \mathbb{Z}$ and $a\in [0,1/3).$ Further assume that $x<0,$ and $y>-2x.$ Is there any significant way to simplify the following: $\left(\sum\limits_{i=\lceil 1/3-(x+a) ...
0
votes
1answer
64 views

A formula for $\sum^n_{i=1}(1+1/n)$?

Find a formula for $$\sum^n_{i=1}\left(1 + \dfrac{1}{n}\right)$$ Prove that it holds for all $n \geq 1$. It kind of looks like is a series but I didn't succeed in this problem. Can someone help me ...
0
votes
1answer
41 views

Compute the following sum

I am to compute the following sum and my professor wrote this on the board. Although I can see what he is doing here and how to use the S and 2S I can't figure out the steps that are highlighted in ...
1
vote
1answer
29 views

Discrete Math Induction: $\sum^n_{i=1} \frac1{i(i+1)}$ [duplicate]

For $\sum^n_{i=1} \frac1{i(i+1)}$ Find a formula and proofs that it holds for all n ≥ 1. How would I find the formula for this one that can hold for all n ≥ 1?
-1
votes
2answers
49 views

Discrete Math On Induction proof: $\sum_{i=1}^n n2^n = (n-1)2^{n+1} + 2$ [duplicate]

Show by induction that the following formulas hold. $\sum_{i=1}^n n2ⁿ = (n-1)2^{n+1} + 2$ What did a similar problem to this but this one is a little different. I think is because this one has a ...
-1
votes
1answer
90 views

Use Mathematical Induction to prove that $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} +…+\frac{1}{n(n+1)}=1-\frac{1}{n+1}$

Use Mathematical induction to prove that for all integers, $n$ is greater than or equal to $1$. I am confused on what to do after I do the the basis step that is using $n$ as $1$. $$\frac{1}{1 \cdot ...
2
votes
0answers
55 views

How to prove these indentities? [closed]

How to prove these indentities? $\displaystyle \sum \limits_{k\geq0} {2n\choose 2k-1}{k-1\choose m-1}=2^{2n-2m+1}{2n-m\choose m-1}$ $\displaystyle \sum \limits_{k=0}^{m} {m\choose k}{n+k\choose ...
2
votes
1answer
46 views

Calculate sum wtih binomial coefficients

I need help with finding the sum of $\sum \limits_{k=0}^{n} \frac{1}{k+1}{n\choose k}x^{k+1}$
0
votes
2answers
40 views

How to calculate this sum

How do you calculate this sum $ \sum \limits_{k=1}^{n} \frac{k}{n^k}{n\choose k}$ ?
3
votes
2answers
59 views

Help finishing proof via induction for a summation

So I have to prove the following equation using induction for n >= 2: $$ \sum\limits_{i=1}^n 4/5^i < 1 $$ However the question asks me to prove something stronger such as this: $$ ...
3
votes
1answer
71 views

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $ To obtain a closed form.

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $? Does it have a closed form? It's the last piece of a puzzle I need to solve a similar question ...
0
votes
2answers
36 views

Compute $\sum_{i=0}^{2n} (-3)^i$ by splitting the series into two parts.

Compute $\sum_{i=0}^{2n} (-3)^i$ by splitting the series into two parts. How do I split it into two parts? All I can tell so far is that the sum is going to be a positive number (probably) because ...
-1
votes
2answers
24 views

Compute the sum $\sum_{i=0}^n 5^{i+1}-5^i$

Compute the sum: $$\sum_{i=0}^n 5^{i+1}-5^i$$ with the hint, "start by writing out (and expanding) the sum." So I did and got $$4 + 20 + 100...$$ with the appearance of going to infinity. Is ...
1
vote
3answers
46 views

Using $S_n = \sum_{k=1}^{n}H_k$ where $H_k$ are the harmonic numbers, show $S_n = (n+1)H_n - n$ [duplicate]

The question: Using $S_n = \sum_{k=1}^{n}H_k$ where $H_k$ are the harmonic numbers, show $S_n = (n+1)H_n - n$. So far I have $S_n = \sum_{k=1}^{n} H_k = \sum_{k=1}^{n} ...
0
votes
3answers
94 views

Derive Closed form sum of N^2

Can anyone explain to me how you would derive this ? I have this question asked in a CS class and can't figure out how to derive it. it has to be derived as you would with sum of N ex ...
2
votes
1answer
61 views

Exponentiation in terms of Summation

For positive integers, $a \times b=\sum\limits^{b}{a}$, correct? So therefore exponentiation where n is also a positive integer should be something like $a^n=\sum\limits^n{\sum\limits^a{a}}$ This is ...
0
votes
7answers
149 views

Calculating $\displaystyle\sum_{i=1}^{n} \binom{i}{2}$

Show $\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to $i!/2!(i-2)!$ and ...
3
votes
0answers
38 views

How to show that $\sum\limits_{k=0}^{\lfloor0.999n\rfloor}\binom{2n}{k} < \binom{2n}{n} $ holds for large n

It seems logical to me since $\binom{2n}{n}$ is in the middle of the row in pascal triangle; therefore, the largest, and for large n the sum adds only the small ones on the left. But I do not have any ...
3
votes
0answers
60 views

Find generating function For sequences

Can anyone out here help? The exercise says: "Find the generating function for each of the sequences below (the general term is given)" Now, the question is how do you find one for those: a) $U_n = ...
1
vote
2answers
55 views

Is $\sum_{x=1}^n (3x^2+x+1) = n^3+2n^2+3n$?

I wanna check if the following equation involving a sum is true or false? How do I solve this? Please help me. $$ \sum_{x=1}^n (3x^2+x+1) = n^3+2n^2+3n$$ for all $n \in \{0,1,2,3, \dots\}$.
2
votes
3answers
95 views

For the Fibonacci sequence prove that $\sum_{i=1}^n F_i= F_{n+2} - 1$

For the Fibonacci sequence $F_1=F_2=1$, $F_{n+2}=F_n+F_{n+1}$, prove that $$\sum_{i=1}^n F_i= F_{n+2} - 1$$ for $n\ge 1$. I don't quite know how to approach this problem. Can someone help and ...
1
vote
4answers
305 views

Calculate sum $\sum\limits_{k=0}k^2{{n}\choose{k}}3^{2k}$.

I need to find calculate the sum Calculate sum $\sum\limits_{k=0}k^2{{n}\choose{k}}3^{2k}$. Simple algebra lead to this ...
6
votes
2answers
94 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,...$ ...
3
votes
0answers
74 views

Product of Summations for All Subsets

We have a set $X$ of $n$ integers $\{$$x_1$, $x_2$, .. , $x_n$$\}$, for which there are $2^n$ total subsets. The summation $s$ of a subset $X'$ is simply the sum of all integers present in $X'$, ...
3
votes
1answer
189 views

Find the sum of the series.

I need to find the following sum: $$\sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s}$$ First I tried to simplify this: $$\begin{split} \sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s} &= ...
7
votes
1answer
122 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity ...
2
votes
1answer
78 views

Concrete Mathematics Reducing sums to closed form

In reducing the sum $S_n = \sum_{1\leq j<k\leq n}(\frac{1}{k-j})$ to a closed form, the authors start by replacing $k$ with $k+j$, such that $S_n = \sum_{1\leq j<k+j\leq n}(\frac{1}{k})$. The ...
0
votes
1answer
45 views

Simplifying a geometric series

I seem to be completely misunderstanding something about the simplification of a geometric series. $$\sum_{j=1}^{n+1} ar^j = \sum_{j=0}^n ar^j + (ar^{n+1}-a)$$ Why does this work? From what I tested, ...
1
vote
1answer
106 views

Mathematic books

Can anyone recommend good books in which I can find information about interesting sums (like Harmonic number, sum of polynomials etc). The only book in which I found any information was Concrete ...
2
votes
2answers
62 views

How to substitute sum variable?

I am not entirely sure how to use variable substitution for a sum. Take the following example: I would like to compute $$\sum_{i=1}^N(2i-1)^2$$ One straightforward way is to split the sum, i.e. ...
1
vote
1answer
69 views

Using Generating Series to Find Sum of Sides of Dice

Question: " Let k be a non-negative integer. Use the theory of generating series to find the expected value of the sum of the dots when k (6-sided) dice are rolled. " I know that the generating ...
1
vote
2answers
92 views

Combinatorial proof with binomial coefficients

I need to prove this with combinatorial arguments. I don't know how to start. $$ \sum_{j = r}^{n + r - k}{j - 1 \choose r - 1}{n - j \choose k - r} = {n \choose k}\,, \qquad\qquad 1\ \leq\ r\ \leq\ ...
0
votes
1answer
44 views

The closed form of a sum of mod(k,m) where k goes from 1 to a arbitrary number.

Is there a closed form for $\sum_{n=0}^{C} mod(n,m)$ for arbitrary integers m ?