This is the full question:     Consider an integer $n\ge 1$ and the integers $i$,$1\le i \le n$. For each $k=0,1,2,\cdots$, find the number of $i$'s that are divisble by $2^k$ but not by $2^{k+1}$.Thus prove $$ \sum_{j=1}^{\infty} \left[ \frac{n}{2^j}+\frac{1}{2} \right] = n$$ and hence that we get the correct value for the sum $\dfrac{n}{2}+\dfrac{n}{4}+\dfrac{n}{8}+\cdots$ if we replace each term by its nearest integer, using the larger one if two exist. Note: $[x]$ denotes the greatest integer function/floor function of $x$.   This is what i did: The number of integers less that $n$ divisible by $m$ are given by $\left[ \dfrac{n}{m}\right]$, those integers will be $m,  2m, \cdots, \left[ \dfrac{n}{m}\right]m$. Hence for the first part of this question, the answer will be precisely $\left[ \dfrac{n}{2^k}\right]-\left[ \dfrac{n}{2^{k+1}}\right]$. But i am not able to see how this helps in proving the given sum. Also i don't understand what the question is trying to say after we have calculated the sum.
122879
I was doing some basic Number Theory problems and came across this problem :     Show that for any integer $n$ $\geq$ $1$ ; $$\sum_{i=0}^\infty [\frac{n}{2^i}+\frac{1}{2}] = 2n$$ ; where $[x]$ represents the greatest integer / floor function   I am all thumbs , even a hint would suffice  P.S. In the  , this question is given in the section on the Greatest Integer Function , perhaps that might help . Also , this is not a homework question , I am just practicing number theory questions on my own from the book
105535
Via induction I need to prove an expression is true. the expression is:  $n \leq 2^k \longrightarrow a_n \leq 3 \cdot k2^k + 4 \cdot  2^k-1$  for all $n,k \in \mathbb{Z^+}$  $a_n$ is a recursive function where  $a_1 = 3$  $a_n = a_{\lfloor \frac{n}{2} \rfloor} + a_{\lceil \frac{n}{2} \rceil} + 3n+1$  I am stuck at the point where I need to prove that $P(n+1)$ is true  $a_{\lfloor \frac{n+1}{2} \rfloor} + a_{\lceil \frac{n+1}{2} \rceil} + 3(n+1) + 1 \leq 3 \cdot k  2^k + 4 \cdot 2^k -1  $   It is the fact that I don't know how to rewrite the floor and ceiling functions to something else.   Can someone give me some ideas how to proceed with this?
101966
I am trying to understand the following problem from Erdős and Surányi's  (Springer), chapter 1 (&quot;Divisibility, the Fundamental Theorem of Number Theory&quot;):  We can multiply two (positive integer) numbers together in the following way. Write the two numbers down next to each other. Divide the first in half, rounding down to an integer, and write the result below it. Double the second number, writing the result below it. We continue this halving / doubling until we are left with $1$ in the first column. Cross out all those numbers in the second column that are opposite an even number and add the remaining numbers in this column together to get the product. Prove that this works.  And this is an example, $73 \cdot 217$:  $(73,217)$ $(36, 434)$ $(18, 868)$ $(9, 1736)$ $(4, 3472)$ $(2, 6944)$ $(1, 13888)$  Then $73 \cdot 217 = 217+1736+13888 = 15841$, which is correct. ... and I really cannot visualize the reason why it works. My thoughts so far:  We are dividing by $2$ in the left column, so only those values that are odd are coming from a division of a previous even number in the left column, and that means that the previous division by $2$ was &quot;perfect&quot;, meaning without decimals.  I can approximate the value of the product of two natural numbers $p \cdot q$ if I divide the first number by $2$ continuously until it arrives at $1$ and multiply the second by $2$ at the same time (so the final value of the second one is an approximation of the product).   But why do we remove some of them for the final sum? I would like to ask the following questions:  How does it work?  We are summing the numbers of the second column that are opposite an odd number. Then what does the sum of the numbers that we do not use from the second column represent?   This is all probably pretty obvious, but I cannot see the light.
44381
My problem is to find the sum of the series $$ S = 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{6}+\frac{1}{8}+\frac{1}{9}+\frac{1}{12}+\cdots $$ where the terms are the reciprocals of the positive integers whose only prime factors are $2$s and $3$s.   I can see that every term in $S$ is of the form $\dfrac{1}{2^m3^n}$ where $m,n\geq 0$. I can also see that each term only occurs once, but I'm not really sure how to use this information effectively. Any ideas (apparently geometric series was a hint)?
58071
So I'm trying to use mathematical induction to show that for all integers $n \ge 1$ ,  $$ 8|(3^{2n} - 1)$$  (is divisible by 8)  I have my base case: [P(1)],  $3^2 - 1 = 9 - 1 = 8$, since $8|8$, the base case proves true  Assume [P(k)], $ 8 | (3^{2k} - 1)$.  I know that I need to show [P(k+1)], $ 8| (3^{2(k+1)}-1) $, but I'm not sure how to prove this. I've only been using induction for summation, so how could I prove divisibility?
60821
Let $M$ be the set of natural numbers that can be written using only $0$ and $1$(in the decimal system). Prove that, for any natural number $k$ $\exists m \in M $ s.t   i) $m$ has exactly $k$ $1$'s, and ii) $m$ is divisible by $k$. (e.g, if $k=3$, then the number $101010 \in M$ is divisible by $3$)    Any hint or solution is welcome. If anyone have any hint in mind please give me step by step. Problem seems to be very interesting to me.
40340
Prove that for any positive integers $m$ and $n$ , there exists a set of $n$ consecutive positive integers each of which is divisible by a number of the form $d^m$, where $d$ is some positive integer not equal to $1$.  I don't know how to approach this question.
114640
Show that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014 without remainder ($i\not=j$).   I think the "pigeonholes" here is the remainder of division by 2014 .  now i need to think of a way to define the "pigeons" but cant think of anything .
98452
Let $x_{1},x_{2},\cdots,x_{n}$ be real numbers. Show that     $$\sum_{i,j=1}^{n}|x_{i}+x_{j}|\ge n\sum_{i=1}^{n}|x_{i}|.$$   I think this problem may be solved using nice methods, but I can't find them yet; I know this may be of use: $$|a|+|b|\ge |a+b|.$$ But I can't make it work. Thank you everyone.
24542
Problem: For positive integers $n,j,k$, prove that the following holds:     $$\left\lfloor\frac 1j\left\lfloor\frac nk\right\rfloor\right\rfloor=\left\lfloor\frac n{jk}\right\rfloor$$     I simply need hints to start on this problem. I have verified that it's indeed true by checking a few examples and I can't seem to find a counter-example, so I'm almost sure that the problem is indeed correct.  However, I can't seem to think of a proper (and rigorous) proof of this. Can someone please help me by giving me a few hints?  I want to prove it myself, so I'd appreciate if people don't directly post the proof themselves. Also, please keep your hints as subtle as possible (there's no fun in proving something if the hint gives out most of the answer) :D
12910
Suppose $n$ be a given positive integer. Then the Diophantine equation $x=n$ has only $1$ solution. Just by inspection, I found that the Diophantine equation $x+2y=n$ has $\left\lfloor \dfrac{n}{2}+1\right\rfloor$ non-negative solutions for $(x,y).$ Also, according to  the Diophantine equation $x+2y+3z=n$ has $\left\lfloor \dfrac{n^2}{12}+\dfrac{n}{2}+1 \right\rfloor$ non-negative solutions for $(x,y).$  Is there any closed form for the number of non-negative integer solutions for $(x_1,x_2,\cdots,x_k)$ of $$x_1+2x_2+3x_3+\cdots+kx_k=n$$ for a given $k\in\Bbb{N}$? How can I prove these formulas rigorously?  EDIT After a very tedious calculation I found that the equation $w+2x+3y+4z=n$ has  $\left\lfloor \dfrac{n^3}{144}+\dfrac{5n^2}{48}+\dfrac{(15+(-1)^n)n}{32}+1 \right\rfloor$ solutions. This solution completely agree with the approximation given by Rus May. However still I believe that we can do something more than this.
9540
Fix integer $n\geq 1$. Consider the number $$1-\binom{n}{2}+\binom{n}{4}-\binom{n}{6}+\cdots$$where the sum continues as long as the lower number in the binomial is $\leq n$. Is there a way to simplify this sum?   The first few values are $1, 0, -2, -4, -4$.
54819
I've been working through a bit of Ireland and Rosen's Number Theory for fun. Problem 4.11 of Ireland and Rosen asks     Prove that $1^k+2^k+\cdots+(p-1)^k\equiv 0\pmod{p}$ if $p-1\nmid k$, and $-1\pmod{p}$ if $p-1\mid k$.    My work is leading where I didn't expect to go. Here I assume $p$ id odd. First, if $p-1\mid k$, then we can wrike $k=(p-1)j$ for some $j$. But then $$ 1^k+\cdots+(p-1)^k\equiv 1^{(p-1)j}+\cdots+(p-1)^{(p-1)j}\equiv \underbrace{1+\cdots+1}_{p-1\text{ times}}=\frac{(p-1)p}{2}\equiv 0\pmod{p} $$ since $p-1$ is even.   Secondly, I suppose $p-1\nmid k$. WLOG, I can assume $0&lt;k&lt;p-1$, Since if $k=(p-1)j+r$ with $0&lt;r&lt;p-1$, then  $$ a^k\equiv a^{(p-1)j+r}\equiv a^r\pmod{p}. $$  Then if $g$ is a primitive root, $$ 1^k+\cdots+(p-1)^k=\sum_{i=1}^{p-1}(g^k)^i=\frac{g^k(1-g^{k(p-1)})}{1-g^k}. $$ Since $g$ is primitive, $p\nmid 1-g^k$, but $p\mid 1-g^{k(p-1)}$, so the above sum is again congruent to $0\pmod{p}$.  So in all cases, I get the sum is congruent to $0$ regardless. Have I messed up, or is there a typo? Thanks.
1550
Consider a set A of 10 integers, $A= \{a_1,a_2, \ldots ,a_{10}\}$. Prove that there is at least one subset of A whose sum is divisible by 10. Use the pigeon-hole principle. Hint: Consider the 10 sums $s_1 = a_1, s_2 = a_1 + a_2, \ldots ,s_{10} = a_1 + a_2 + \ldots+a_{10}$. If one of these ten sums is divisible by $10$, we are done. So assume that none of these ten sums is divisible by $10$.  I'm pretty sure this is the proof but im not exactly sure what's $b_l$ and $b_k$ stand for?    Let $A=\{a_1,a_2,...,a_{10}\}$ Define set of numbers $b_n=\sum\limits_{i=1}^n a_n$ i.e. the set $$\{a_1, (a_1+a_2),(a_1+a_2+a_3),\ldots ,(a_1+a_2+\ldots +a_{10})\}$$ If any element of the set is divisible by $10$, then we are done.  Hence proving case $1$.  Case 2: Assume that no element of this set is disible by $10$.  Then, by Pigeon hole priciple, there exists some $k&lt;l$, such that, $b_l\equiv b_k$   then $b_l\equiv b_k (mod 10)$ with $l&gt;k&gt;0$   Hence, $\{b_k,b_{k+1}, \ldots,b_l\}$ is a subset of $A$ whose sum is divisble by $10$. Thus proving Case $2$.
31037
An  which I am not able to solve.  Let $\mathsf{S_{n}}$ denote the $n$-th partial sum of the series: $$\sum\limits_{r=1}^{\infty} \frac{1}{r(r+1)}$$  Prove that for every integer $k&gt;1$, there exists integers $m$ and $n$, such that $$s_{m}-s_{n} =\frac{1}{k}$$
46688
Here is an argument in my book.  Theorem If $n$ is a positive integer and $p$ is a prime, then the exponent of the highest power of p that divides $n!$ is $\sum_{k=1}^\infty [\frac{n}{p^k}]$ Proof&gt; Among the first $n$ positive integers, those divisible by $p$ are $p,2p,...,[n/p]p$. Thus, (Q1) there are exactly $[n/p]$ multiples of $p$ occurring in the product that defines $n!$, namely, $p,2p,...,[n/p]p$. The exponent of $p$ in the prime factorization of $n!$ is obtained by adding to the number of integers in $\{p,2p,...,[n/p]p\}$, the number of integers among $1,2,\cdots,n$ divisible by $p^2$, and so on. Reasoning as in the first paragraph, the integers between 1 and n that are divisible by $p^2$ are $p^2,\cdots,[n/{p^2}]p^2$. After a finite number of repetitions of this process, we are led to conclude that the total number of times $p$ divides $n!$ is $\sum_{k=1}^\infty [\frac{n}{p^k}]$  I completely don't get this argument from $(Q1)$. Why there are exactly $[n/p]$ multiples of $p$ in the prime factorization of $n!$?? Moreover, I don't get what the author is doing after $(Q1)$. Could someone please explain this argument in detail? Or please suggest me a link to see a proof for this theorem. I have googled it, but I couldn't find a proof for it. EDIT: I hate explaining things verbally. Please give me a formal argument..
42920
The problem is as follows: Prove that $$1^2 + 2^2 + 3^2 + \cdots + (n-1)^2 \equiv 0 \, \text{mod n} \ \text{if and only if } n \equiv \pm 1 \, \text{mod} 6.$$  My idea is to of course rewrite the summation. We have $$1^2 + 2^2 + 3^2 + \cdots + (n-1)^2 = \frac{(n-1)n(2n-1)}{6}.$$  Now, in order for this to be an integer, must we have in particular that $6 \mid n-1 \Rightarrow n \equiv 1 \, \text{mod} 6$?  We also know that the sum $$1^2 + 2^2 + 3^2 + \ldots + (n-1)^2 + n^2 = \frac{n(n+1)(2n+1)}{6}.$$ Must we have in particular that then $6 \mid n+1 \Rightarrow n \equiv -1 \, \text{mod} 6$?  I think the statement holds if and only if the whole way so we are done with both ways?