How to show this  $$\sum_{k=0}^{n-1} [x+\frac{k}{n}]= [nx]$$ for every $x\in \mathbb{R}, n\in\mathbb{N}$. Where the function $[x] = \max\{p \in\mathbb{N}: p\leq x\}$ is the floor function?
4448
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 part of $x$ is the unique $z\in \Bbb Z$ such that $$z\leq x &lt; z+1$$ and we denote it by $[x]$.   Now he asks to prove some basic things about it, such as: if $n\in \Bbb Z$, then $[x+n]=[x]+n$  So I proved it like this: Let $z=[x+n]$ and $z'=[x]$. Then we have that  $$z\leq x+n&lt;z+1$$  $$z'\leq x&lt;z'+1$$  Then $$z'+n\leq x+n&lt;z'+n+1$$  But since $z'$ is an integer, so is $z'+n$. Since $z$ is unique, it must be that $z'+n=z$.  However, this doesn't seem to get me anywhere to prove that  $$\left[ {2x} \right] = \left[ x \right] + \left[ {x + \frac{1}{2}} \right]$$  in and in general that   $$\left[ {nx} \right] = \sum\limits_{k = 0}^{n - 1} {\left[ {x + \frac{k}{n}} \right]} $$  Obviously one could do an informal proof thinking about "the carries", but that's not the idea, let alone how tedious it would be. Maybe there is some easier or clearer characterization of $[x]$ in terms of $x$ to work this out.  Another property is $$[-x]=\begin{cases}-[x]\text{ ; if }x\in \Bbb Z \cr-[x]-1 \text{ ; otherwise}\end{cases}$$  I argue: if $x\in\Bbb Z$, it is clear $[x]=x$. Then $-[x]=-x$, and $-[x]\in \Bbb Z$ so $[-[x]]=-[x]=[-x]$. For the other, I guess one could say:  $$n \leqslant x &lt; n + 1 \Rightarrow  - n - 1 &lt; x \leqslant -n$$  and since $x$ is not an integer, this should be the same as $$ - n - 1 \leqslant -x &lt; -n$$  $$ - n - 1 \leqslant -x &lt; (-n-1)+1$$  So $[-x]=-[x]-1$
74920
Suppose that $0\neq x\in\mathbb{R}$ and $x + \frac1x\in\mathbb{Z}$. Prove that, for all  $n\ge1$, $x^n + \frac1{x^n}\in\mathbb{Z}$.  I can't figure out and understand the question. Can you give me some hints ?
101508
Let $0 \leq p \leq 1$, $n \in \mathbb{N}_0$ and consider $$\sum_{i = 0}^{\lfloor n/2 \rfloor} {n \choose 2i}p^{2i}(1 - p)^{n - 2i}$$ Has anyone a hint for me how I can calculate the sum?
52987
I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated.    Question Let the number of partitions be given by the function $p(n)$, i.e. the number of ways of writing the integer $n$ as a sum of positive integers. Prove that that if $g$ is any polynomial function in $n$, then there exists an integer $N$ such that $g(n)&lt;p(n)$ for all $n&gt;N$. Do not use the asymptotic Hardy-Ramanujan formula.    Provided Proof.    Enough to show $n^a&lt;p(n)$ for fixed positive integer $a$. (This is just saying that we want to show $p(n)$ grows faster than any degree polynomial of $n$, right?) We have that $(i_1,i_2,\ldots,i_{a+1},1^{n-i_1-\cdots -i_{a+1}})$ is a partition of $n$ as long as $i_{a+1}\leq i_a\leq \cdots i_1 \leq \lfloor\frac{n}{a+1}\rfloor$. (I really don't understand this step. What is this partition? Of the coefficients or terms of polynomial $p(n)$? And how do we know this is $\leq \lfloor\frac{n}{a+1}\rfloor$?) The number of partitions $n$ of this form is multiset binomial coefficient $$\left(\dbinom{\lfloor \frac{n}{a+1}\rfloor}{a+1}\right)=\frac{\lfloor\frac{n}{a+1}\rfloor(\lfloor\frac{n}{a+1}\rfloor+1)\cdots(\lfloor\frac{n}{a+1}\rfloor+a-1)}{(a+1)!}$$ (I'm assuming that if I can understand (2.) then I can understand this line) This means $p(n)&gt;\left(\binom{\lfloor \frac{n}{a+1}\rfloor}{a+1}\right)$ for all $n&gt;0$. Since $a$ is constant, the given fraction grows with order $n^{a+1}$, which means $p(n)&gt;n^a$ for $n$ sufficiently large. (Why does it grow with order $n^{a+1}$?)   Thanks all again in advance!
79603
Give a convincing argument that $\lfloor x\rfloor + \lfloor y\rfloor \leq \lfloor x+y\rfloor$ for every pair of numbers $x$ and $y$. Could someone please explain how to prove this? I attempted to say that the largest values that could be added to $x$ and $y$ is $0.99$ and that doing so still made $\lfloor x\rfloor + \lfloor y\rfloor &lt; \lfloor x+y\rfloor$. However, my answer was not accepted.
53752
So I'm trying to do a proof for this problem:  If $\displaystyle{k \le \left\lfloor \frac{n}{2} \right\rfloor}$ then $$\displaystyle{\binom{n}{k-1} &lt; \binom{n}{k}}$$  I can do it algebraically but my professor asked for a combinatorial proof.  How would one does it?
57494
Let $x\in\mathbb{Q}$ with $x&gt;0$.  Prove that we can find $n\in\mathbb{N}^*$ and distinct $a_1,...,a_n \in \mathbb{N}^*$ such that $$x=\sum_{k=1}^n{\frac{1}{a_k}}$$
50345
Prove the following identity:   $$\lfloor x\rfloor +\lfloor x+\frac{1}{n}\rfloor +\lfloor x+\frac{2}{n}\rfloor +\lfloor x+\frac{3}{n}\rfloor+...+\lfloor x+\frac{n-1}{n}\rfloor =\lfloor nx\rfloor$$ where n is a Natural Number.   $$$$At first I thought of splitting it into 2 cases: when x is an integer, and when x isnn't an integer. The case of $x$ being an integer is quite simple: $\lfloor x+\frac{k}{n}\rfloor=x$ for $0\le k\le n-1$. Thus the LHS becomes $n\lfloor x\rfloor$ which is equal to the RHS. $$$$However I do not know how to go about the case of $x$ not being an integer.  Lastly, I would actually prefer a proof where it is not necessary to make cases based on the values of $x$, but to have one general proof which satisfies all $x$.  Could somebody please show me how to complete the proof in both ways (ie first, the case where $x$ isn't an integer, and secondly the general proof which doesn't involve breaking into cases)? Many thanks in advance!
8724
Let $S(n)$ be $S(n)=\left\{k\;\left|\;\left\{\frac{n}{k}\right\}\right.\geq \frac{1}{2}\right\}$,where $\{x\}$ is the fractional part of $x$  Prove that :  \begin{align} \sum_{k\in S(n)} \varphi(k)=n^2 \end{align}  maybe the fact \begin{align} \sum_{k \leq 2n}\left\lfloor{\frac{n}{k}+\frac{1}{2}}\right\rfloor \varphi(k)=\frac{3n^2+n}{2}\end{align}  and \begin{align} \sum_{k \leq 2n}\left\lfloor{\frac{n}{k}}\right\rfloor \varphi(k)=\frac{n^2+n}{2}\end{align}  can help, but I can't prove these two equations    Edited:Sorry that my question is to prove the two equation before, because I've already known how to relate the problem with these two equations, and I've also known how to prove the second equation from  but I can't solve the first one with the similar method.
70466
Given $x\in\mathbb R_+$ and $m,n\in\mathbb Z_+$, is it true that $$\bigg\lfloor\frac{\lfloor \frac{x}{m}\rfloor}{n}\bigg\rfloor=\bigg\lfloor \frac{x}{mn}\bigg\rfloor?$$    Thanks for at least three different and convincing proofs! I'll use this result  trying to code the prime counting formula from Wikipedia $(2)$:  Given $m$, select $y$ so that  $\sqrt[3]{m}\le y\le\sqrt{m}$ and let $n=\pi(y)$. Then  $(1)\;$ $\pi(m)=\phi(m,n)+n-1-P_2(m,n)$, where  $(2)\;$ $\displaystyle \phi(m,n)=\phi(m,n-1)-\phi\Big(\frac{m}{p_n},n-1\Big)$,  $\;\phi(m,0)=\lfloor{m}\rfloor$ and  $(3)\;$ $\displaystyle P_2(m,n)=\sum_{y&lt;p\le\sqrt{m}} \Big(\pi\Big(\frac{m}{p}\Big)-\pi(p)+1\Big)$, $\;p$ is a prime.
100263
I'm trying to show that      $$\sum_{k=0}^n (-1)^k\frac{{ {n}\choose{k}}}{{ {x+k}\choose{k}}} = \frac{x}{x+n}$$   I've tried expanding this using definition of binomial coefficient, then binomial expansion, now I'm using induction to simplify $\sum_{k=0}^m (-1)^k\frac{{ {n}\choose{k}}}{{ {x+k}\choose{k}}}$, but it looks very inelegant, is there a better way?
18108
We take place on $\mathbb C(x_1,...,x_r,x'_1,...,x'_p,u_0,...,u_r,u'_0,...,u'_p)$ with $r,p\in \mathbb N$     Show that :   $$\displaystyle{\sum_{i=1}^r \left(   \frac{\prod_{j=0}^r (u_j-x_i) \prod_{j=1}^p (x'_j-x_i) }{  \prod_{1\leq j\leq r, j\neq i     }(x_j-x_i) \prod_{j=0}^p (u'_j-x_i)}      \right)}-\displaystyle{\sum_{i=0}^p \left(   \frac{\prod_{j=0}^r (u'_i-u_j) \prod_{j=1}^p (u'_i-x'_j) }{  \prod_{0\leq j\leq p, j\neq i     }(u'_i-u'_j) \prod_{j=1}^r (u'_i-x_j)}      \right)}=\displaystyle{\sum_{i=1}^p x'_i +\sum_{i=0}^r u_i -\sum_{i=1}^r x_i-\sum_{i=0}^p u'_i}$$   I have seen this exercise in an old book at the library. Unfortunately there was no indication how can I solve the problem.   Anyway if someone can give me some ideas it will be greatful.   NB: Sorry for the title, I have not had other ideas
97524
Let $T_n$ be a random variable with $T_n=X_1+...+X_n$ where the $X_i$'s are iid. Further we set $N(t)=max\{ n: T_n\leq n\}$ with the property $\Pr(N(t)&lt;\infty)=1$.  I want to prove that $\mathbb{E}[N(t)]&lt;\infty$.   I have done this so far. Let $F_n$ be the distribution function of $T_n$. $$\mathbb{E}[N(t)]=\sum_{n=1}^{\infty} n P(N(t)=n)=\sum_{n=1}^{\infty} n (F_n(t)-F_{n+1}(t))=\sum_{n=1}^{\infty} F_n(t)$$  Further I know that $0 \leq F_n \leq 1$. But does this implies $\mathbb{E}[N(t)]&lt;\infty$ ? I don't think so... I don't know what I can do further...   Can anybody help me how I can proof it?   Thank you for any help!!!
69428
Does anyone know what is the sum function $f(x)$ of the series $\displaystyle\sum_{n=1}^\infty \frac{\cos(nx)}{n^2}$? I have no idea how to find a sum function... Any help would be appreciated.
24379
I'm currently sitting with the following number theory problem:  Prove that for all $X \geq 1$, $$\sum_{1 \leq n \leq X} \mu(n) \left[\frac{X}{n}\right] = 1.$$  A few ideas I have tried: Using that $[x]=x - \{x\}$ which I couldn't make out to bring anything. Switching around on the summation variables, like $$\sum_{d \leq N} \mu(d) f\left( \frac{n}{d} \right) = \sum_{d \leq N} \mu \left( \frac{d}{n} \right) f(d)$$ but that didn't seem to bring anything.  I tried writing out the first few terms, which give $$\mu(1) [X] - \left[\frac{X}{2}\right] - \left[\frac{X}{3}\right] - \left[\frac{X}{5}\right] + \left[\frac{X}{6}\right] - \left[\frac{X}{7}\right] - \left[\frac{X}{8}\right]$$ but I can't seem to find a system where it simply reduces to one!  What do you think?
86548
Prove that: $$6 \not\left|\ \left\lfloor\frac 1 {(\sqrt[3]{28} - 3)^{n}}\right\rfloor \ (n \in Z^+)\right.$$ ($\lfloor x\rfloor$ = largest integer not exceeding $x$)  I am very bad as English and number theory, please help me
73806
I'm reading a book about proofs and I'm currently stuck in this problem.  Prove that for all real numbers $x$ and $y$ we have that: $$\lfloor x\rfloor \lfloor y\rfloor \leq \lfloor xy\rfloor \leq \lfloor x\rfloor \lfloor y \rfloor + \lfloor x \rfloor + \lfloor y \rfloor$$  I though I could do it by cases, considering when the number is a pure integer and when is an integer plus some real number. But by doing this I end up with having a lot of cases to show. Is there any better, simpler and clever approach? Thank you!  PS: I end up with a lot of cases because there is a point where I will have to consider "subcases" of cases specifically when the integer part is multiplying with the positive "rest" less than one