0
votes
1answer
34 views

Value of an iterated sum

I am interested in the number of function evaluations required to numerically evaluate an iterated integral of the form $$ \int_0^t \int_{t_1}^t \cdots \int_{t_{n-1}}^t f(t_1,\ldots,t_n) dt_n\cdots ...
4
votes
4answers
72 views

Find the sum of the multiples of $3$ and $5$ below $709$?

I just cant figure this question out: Find the sum of the multiples of $3$ or $5$ under $709$ For example, if we list all the natural numbers below $10$ that are multiples of $3$ or $5$, we get $3$, ...
3
votes
2answers
43 views

A sum of difference of floors

I have the sum ( $M$ is any integer $> 1$ ): $$ \sum_{h = 1}^{M}\left(\,\left\lfloor\, 2M + 1 \over h\,\right\rfloor -\left\lfloor\, 2M \over h\,\right\rfloor\,\right) $$ and looking for a way to ...
3
votes
2answers
148 views

Evaluation of the sum $\sum_{i=1}^{\lfloor na \rfloor} \left \lfloor ia \right \rfloor $

Let $a$ be a positive proper fraction and $n$ is any integer then evaluate the following sum, $$\sum_{i=1}^{\left \lfloor na \right \rfloor\atop} \left \lfloor ia \right \rfloor $$ I think that ...
4
votes
1answer
155 views

Interesting Sum Congruence

Let $5\mid a$, $\gcd(a,b)=1$, and $b\equiv 2\bmod 5$. How can one show that $\sum_{k=1}^{a}k\lfloor\frac{kb}{a}\rfloor\equiv 2\bmod 5$? Similarly, can we show that if instead $b\equiv 3\bmod 5$, then ...
2
votes
0answers
113 views

Evaluate this product $n \times \frac{n-1}{2} \times \dots \times \frac{n-(2^k-1)}{2^k}$

For $k = \lfloor \log_{2}(n+1) \rfloor - 1$ evaluate $n \times \frac{n-1}{2} \times\frac{n-3}{4} \times \frac{n-7}{8} \times \dots \times \frac{n-(2^{k}-1)}{2^k}$ So the product goes up to $k$ and I ...
5
votes
1answer
63 views

How many decimal representations are possible for the number 1

I know that there at least two $0.\overline{9}$ and 1 Is there a neat and more concrete way to understand this problem.
0
votes
1answer
20 views

Limits on repeated sum in circle method

In Bob Vaughan's book The Hardy-Littlewood Method, early on he gives a sum \begin{equation} \left(\sum_{m=1} ^N e(\alpha m^k)\right)^s = \sum_{m_1 = 1} ^N \sum_{m_2 = 1} ^N \cdots \sum_{m_s = 1} ^N ...
1
vote
0answers
20 views

An inequality involving Möbius function [duplicate]

For any positive integer $n$ show the inequality holds : $$\left|\sum_{i=1}^{n}\frac{\mu(i)}{i}\right|\le 1$$ I tried induction. when $\mu(n+1)=0$ it is trivial. But what if $\mu(n+1)\ne 0$? I am ...
0
votes
1answer
48 views

Upper bound for the sum $ \sum_{k=1}^N \frac{1}{\varphi(k)}$

Is there an upper bound for the sum $$ \sum_{k=1}^N \frac{1}{\varphi^{\alpha}(k)} $$ where $\varphi(n)$ is the Euler totient function and $\alpha\geq 1$ a real constant? In particular, I'm interested ...
3
votes
1answer
36 views

Limit of an unusual function?

First, I define the function, $f(k)=1$ if the sum of the factors of $k$ (excluding $k$) is greater than $k$, $f(k)=-1$ if the sum of the factors of $k$ (excluding $k$) is less than $k$, and $f(k)=0$ ...
4
votes
1answer
130 views

$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$ isn't divisible by 5

I have no idea Prove that for any $n$ natural number this sum $$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$$ isn't divisible by $5$. $\begin{array}{l} \left( {1 + x} \right)^{2n + 1} - ...
1
vote
1answer
55 views

Proof for $\sum_{x=1}^{n-1}\left\lfloor \dfrac{mx}{n}\right\rfloor=\dfrac{(n-1)(m-1)}{2}$ where $(m,n)=1$

This identity might be well-known, but I could find the proof neither by myself not by searching it in Internet. Could you describe an outline of solution?
3
votes
1answer
38 views

$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}}$

I'm supopsed to show that if $m$ and $n$ are non-negative integers then $$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}} = \left\{ \begin{array}{l l} 1 & \quad \text{if $n=0$}\\ ...
1
vote
2answers
78 views

Find $\sum\frac{a(n)}{n(n+1)}$, where $a(n)$ — number of 1's in binary expansion of n. [duplicate]

Let $a(n)$ is a number of 1's in binary expansion of n, find the sum $$ \sum\limits_{n=1}^{\infty}\frac{a(n)}{n(n+1)}. $$
14
votes
1answer
125 views

How to sum this infinite series

How to sum this series: $$\frac{1}{1}+\frac{1}{11}+\frac{1}{111}+\frac{1}{1111}+\cdots$$ My attempt: Multiply and divide the series by $9$ ...
2
votes
1answer
66 views

Help with $\sum_{d\mid n}τ(d)^2=\sum_{d \mid n}τ(d)^3$

I am doing some exercises on number theory on multiplicative number theoretic functions and I have some problems with the multiplication on sums like the sum $\sum_{d\mid n}(τ(d))^2$ where $d$ is a ...
3
votes
3answers
84 views

The sum $1!+2!+3!+…+2007!$ is not a perfect square

Today my teacher told me to prove this:- Prove that $1!+2!+3!+...+2007!=\sum_{n=1}^{2007}(n!) $ is neither a perfect square nor a perfect cube. Not getting any idea. Please help. Thanks in advance.
3
votes
1answer
60 views

Number of palindromic numbers less than a power of $10$

I noticed that every $10^{n}$ there is a certain number of palindromic numbers that I collected in this sequence: $$S=\{a_n,a_{n+1},a_{n+2}...\}=\{10,9,90,90,900,900...\}$$ where every number $a_n$ is ...
1
vote
2answers
72 views

summation of ceil and floor function

I need a closed solution or a faster algorithm for calculating $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k}-1 \right\rceil $$ and $$ \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor $$ where $ ...
4
votes
5answers
102 views

How can I find integers $n \gt 1$ such that the average of $1^2,2^2,3^2…n^2$ is itself a perfect square.

$\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$ so we would like to solve $6k^2=(n+1)(2n+1)$ here we see that $6|(n+1)(2n+1)\implies 2|n+1$ hence we can set $n=2j-1$ $2j(4j-1)=6k^2\implies ...
4
votes
1answer
91 views

How can I prove that $\frac{\sigma(n)}{n} = \sum_{(d|n)} \frac{1}{d}$ for every $n \in \mathbb{Z^{+}}$?

I want to show that $\displaystyle \frac{\sigma(n)}{n} = \sum_{(d|n)} \frac{1}{d}$ for every $n \in \mathbb{Z^{+}}$. This is essentially a basic number theory question. I am able to get to the ...
11
votes
2answers
221 views

A different Harmonic series.

Let's call the following numbers than can be produced by playing with plus and minus: $$H_n'=\pm\frac{1}{1}\pm\frac{1}{2}\pm\frac{1}{3}\pm\cdots\pm\frac{1}{n}$$ "Harmonic kids" of $H_n$. We have a ...
7
votes
1answer
131 views

Find all natural numbers such that $\sum_{k=1}^{n} \frac{n^k}{k!}$ is an integer

Find all natural numbers such that $\sum_{k=1}^{n} \frac{n^k}{k!}$ is an integer. I've tried to bring all fractions under commmon denominator and it didn't helped me much. With guessing I find out ...
4
votes
2answers
69 views

Finding the summation of the floor of the series identity

I would appreciate if somebody could help me with the following problem: Q: How to proof ? The number of positive divisors of $n$ is denoted by $d(n)$ ...
3
votes
2answers
164 views

Summation involving totient function: $\sum_{d\mid n} \varphi(d)=n$ [duplicate]

Prove that:$$\sum_{d\mid n} \varphi(d)=n$$ Where $\varphi(n)$ denotes the number of positive integers $m$ less than or equal to $n$ such that $\gcd(m,n)=1$ I am lost here, any help would be ...
3
votes
1answer
62 views

On $\lfloor\sqrt n \rfloor+ \sum_{j=1}^n \lfloor n/j\rfloor$

How do we prove that $\Big[\sqrt n \Big]+ \sum_{j=1}^n \bigg[ \dfrac nj\bigg]$ is an even integer for all $ n \in \mathbb N$ ? (where $\Big[ \space \Big]$ denotes the "greatest integer" function)
2
votes
2answers
110 views

Totient function sum over divisors

I would like to know if there is a closed form solution for $$G(n)=\sum\limits_{d\mid n}(-1)^{\frac{n}{d}}\phi(d)$$ It seems quite likely there is since $$\sum\limits_{d\mid n}\phi(d)=n$$ But I ...
5
votes
2answers
617 views

Proving $\sum_{k=1}^n{2k-1\choose k}{2n-2k+1\choose n-k+1}=4^n-{2n+1\choose n+1}$

Some background. I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that ...
5
votes
1answer
83 views

Hockey Classics at Matheletics '13

I'm trying to solve a challenge from Matheletics '13: Micheal Nobbs is organizing a training camp for identifying new talents in Indian Hockey. The camp witnessed a total of ($3K+1$) players. Each of ...
2
votes
1answer
38 views

Is $\frac{k!!}{j!!(k-j)!!}\leq\frac{k!}{j!(k-j)!}$ for all integers $j$ and $k$, where $0\leq j\leq k$?

For all integers $j$ and $k$, where $0\leq j\leq k$, is the inequality $\frac{k!!}{j!!(k-j)!!}\leq\frac{k!}{j!(k-j)!}$ true? I have a feeling that it is and it would be helpful to me if it is, ...
2
votes
1answer
42 views

Number of factors of summation

Let $a(n)$ be the number of $1$'s in the binary expansion of $n$. If $n$ is a positive integer, show that $$\Bigg|\sum_{k=0}^{2^n-1}(-1)^{a(k)}\times 2^k\Bigg|$$ has at least $n!$ divisors. I think ...
3
votes
2answers
202 views

Finding a closed form for a sum involving floor function $\sum\limits_{k=1}^nk\lfloor km/n\rfloor$

Given integers $m,n$, is there a known closed form for the sum $\sum\limits_{k=1}^nk\lfloor km/n\rfloor$? and if not, is it possible to show there is no closed form for this sum? I've attempted to ...
10
votes
2answers
120 views

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $\sum_{k=1}^n\frac{a_k-b_k}k$

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $$\sum_{k=1}^n\frac{a_k-b_k}k$$ By computing some partial sums, the answers are 0. It seems an inductive argument is possible.
2
votes
1answer
228 views

Sums of Primitive Roots and Quadratic Residues when $p \equiv 3\pmod 4$

Define $$R_{p}=\{ r \mid r: \text{primitive root of p}, 1 \le r \le p \}$$ and also $$Q_{p}=\{ a \mid a: \text{quadratic residue of p}, 1 \le a \le p \}$$ $$Q_p^c=\{a \mid a: ...
2
votes
1answer
130 views

Simple Divisor Sum Transformation by Changing the Order of Double Summation

Show that $$\sum_{d|n} \frac{n}{d} \sigma(d) = \sum_{d|n} d \tau(d)$$ by changing the order of summations from each side to the other. $\sigma$ and $\tau$ are divisor sum functions. ...
6
votes
2answers
142 views

Simple Divisor Summation Inequality (with Moebius function)

Show that $$\left| \sum_{k=1}^{n} \frac {\mu(k)}{k} \right| \le 1 $$ where $\mu$ is Moebius function and n is a positive integer. The hard thing here is that the sum is not directly ...
5
votes
5answers
456 views

Show $\sum\limits_{d|n}\phi(d) = n$. [duplicate]

Show $\sum\limits_{d|n}\phi(d) = n$. Example : $\sum\limits_{d|4}\phi(d) = \phi(1) + \phi(2) + \phi(4) = 1 + 1 + 2 = 4$ I was told this has a simple proof. Problem is, I can not think of a way to ...
1
vote
2answers
149 views

Representing an Integer as a Sum of at Most $k$ Triangular Numbers

What is the smallest $k$ such that every $n \in \mathbb{N}$ can be represented by a sum of exactly $k$ triangular numbers? For the sake of simplicity, I will assume $0$ is a triangular number. I've ...
3
votes
2answers
143 views

On proving the convergence of $1/n^2\sum_{1\le k\le n}\varphi(k)$

Let $$\Phi_n=\frac{1}{n^2}\sum_{k=1}^n\varphi(k).$$ How one can show that $\Phi_n$ is convergent sequence? (Here, $\varphi$ denotes the Euler's totient function.) And please, without any monster ...
1
vote
1answer
91 views

Critique on a proof by induction that $\sum_{i=1}^n i^2= n(n+1)(2n+1)/6$?

I need to make the proof for this 1:$$1^2 + 2^2 + 3^2 + ... + n^2=\frac{(n(n+1)(2n+1))}{6}$$ By mathematical induction I know that, If P(n) is true for $n>3^2$ then P(k) is also true for k=N and ...
2
votes
0answers
58 views

Is my proof correct? (Also formally)

Hello dear community! I just worked on a problem in my discrete mathematics text book and wondered if my approach to a specific exercise is correct. There are no solutions to it, that's the reason I ...
0
votes
2answers
63 views

Criteria for divisibility by 9

Prove the following criteria for divisibility by 9: If $a = \sum\limits_{i=0}^n(c_i10^i)$, where $c_i \in \mathbb{N}$ and $0 \leq c_i < 10$, then $9|a \iff 9|\sum\limits_{i=1}^nC_i$.
2
votes
1answer
39 views

Show $\displaystyle\sum_{k=N_{1}}^{N_{2}-1} k^{s_0}\left(\frac{1}{k^s}-\frac{1}{(k+1)^s}\right) \rightarrow0$ as $N_1, N_2 \rightarrow \infty$

Show $\displaystyle\sum_{k=N_{1}}^{N_{2}-1} k^{s_0}\left(\frac{1}{k^s}-\frac{1}{(k+1)^s}\right) \rightarrow0$ as $N_1, N_2 \rightarrow \infty$, where $s \gt s_0 \ge0$ and $k, N_1, N_2 \in ...
3
votes
3answers
85 views

for every integer $n \ge 1$ one has the equality

Could any one help me? For every integer $n \ge 1$ one has the equality: $$ 1-{1\over 2}+ {1\over 3}-{1\over 4}+\dots+{1\over 2n-1}-{1\over 2n}={1\over n+1}+{1\over n+2}+\dots +{1\over 2n}.$$ ...
14
votes
11answers
2k views

Can the factorial function be written as a sum?

I know of the sum of the natural logarithms of the factors of n! , but would like to know if any others exist.
4
votes
2answers
249 views

summation of consecutive natural numbers does not end in 7,4,2,9

I calculated sum of n consecutive natural numbers where n = 1 to 100 .What I mean is $$\sum_{n=1}^{1}n = 1 $$ $$\sum_{n=1}^{2}n = 3 $$ $$\sum_{n=1}^{3}n = 6 $$ And I got answers and noticed that ...
1
vote
1answer
595 views

Evaluating $\sum_{i=0}^{m-1} [ \frac{b + ia}m ]$

Let $a,b\in\mathbb{Z}$ and $m\in\mathbb{Z}_{>1}$ Evaluate $[\frac {b}{m}] + [\frac {(b+a)}{m}]+ [\frac {(b+2a)}{m}]+ [\frac {(b+3a)}{m}]+ [\frac {(b+4a)}{m}]+ [\frac {(b+5a)}{m}]+.....+ [\frac ...
2
votes
4answers
131 views

$\sum_{k=1}^n m(k)$, where $m(k)$ is defined by $2^{m(k)} || k$.

I'm looking at the sum: $$f(n) = \sum_{k=1}^n m(k),$$ where $m(k)$ is defined by $2^{m(k)} || k$, i.e. $2^{m(k)}$ is the largest power of $2$ that divides $k$. For example, we have $f(8) = ...
9
votes
2answers
199 views

Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$

I realize there is probably not a closed form, but is there an efficient way to calculate the following expression? $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$ I've noticed $$\sum_{k=1}^n ...