Mixing
Prove that $sumlimits_{k=1}^nlfloor n/krfloor+lfloor sqrt{n} rfloor$ is even. [duplicate]
$begingroup$
This question already has an answer here:
How to show that $lfloor n/1rfloor+lfloor n/2 rfloor+…+lfloor n/nrfloor+lfloor{sqrt{n}}rfloor$ is even?
1 answer
Let $n$ be a natural number. Prove that
$displaystyle sum_{k=1}^nlfloor n/krfloor+lfloor sqrt{n} rfloor$ is even.
I tried to introduce the fractional part, but it didnt help me.
Next, I considered an inequality to create a bound, but that too was in vain. Next I found out that $lfloor x rfloor = lfloor x/2 rfloor +lfloor x+1/2 rfloor$.
I applied this, but as all were as a sum, it became hard for me to cancel out and it made my work difficult. Now the next problem is about the square root in the box. I once saw in an example that
$$lfloor sqrt{n}+ sqrt{n+1} rfloor = sqrt{4n+1}$$
Now even if this may seem useful, I cannot understand how to remove the $lfloor sqrt{n+1} rfloor $ from the identity. Any help would be helpful!
elementary-number-theory summation floor-function
edited Feb 1 at 13:46
Martin Sleziak
44.8k10119273
$endgroup$
marked as duplicate by rtybase, Community♦ Jan 21 at 15:50
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
How to show that $lfloor n/1rfloor+lfloor n/2 rfloor+…+lfloor n/nrfloor+lfloor{sqrt{n}}rfloor$ is even?
1 answer
Let $n$ be a natural number. Prove that
$displaystyle sum_{k=1}^nlfloor n/krfloor+lfloor sqrt{n} rfloor$ is even.
I tried to introduce the fractional part, but it didnt help me.
Next, I considered an inequality to create a bound, but that too was in vain. Next I found out that $lfloor x rfloor = lfloor x/2 rfloor +lfloor x+1/2 rfloor$.
I applied this, but as all were as a sum, it became hard for me to cancel out and it made my work difficult. Now the next problem is about the square root in the box. I once saw in an example that
$$lfloor sqrt{n}+ sqrt{n+1} rfloor = sqrt{4n+1}$$
Now even if this may seem useful, I cannot understand how to remove the $lfloor sqrt{n+1} rfloor $ from the identity. Any help would be helpful!
elementary-number-theory summation floor-function
edited Feb 1 at 13:46
Martin Sleziak
44.8k10119273
$endgroup$
marked as duplicate by rtybase, Community♦ Jan 21 at 15:50
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
$begingroup$
Please format your question through latex.
$endgroup$
– lightxbulb
Jan 21 at 15:17
$begingroup$
I do not know how to use latexx
$endgroup$
– user636268
Jan 21 at 15:20
1
$begingroup$
math.meta.stackexchange.com/questions/5020/…
$endgroup$
– lightxbulb
Jan 21 at 15:20
$begingroup$
Do you mean $lfloor x rfloor$? You did mention largest integer not exceeding $x$.
$endgroup$
– Mohammad Zuhair Khan
Jan 21 at 15:21
$begingroup$
Yes the floor function
$endgroup$
– user636268
Jan 21 at 15:22
add a comment |
$begingroup$
This question already has an answer here:
How to show that $lfloor n/1rfloor+lfloor n/2 rfloor+…+lfloor n/nrfloor+lfloor{sqrt{n}}rfloor$ is even?
1 answer
Let $n$ be a natural number. Prove that
$displaystyle sum_{k=1}^nlfloor n/krfloor+lfloor sqrt{n} rfloor$ is even.
I tried to introduce the fractional part, but it didnt help me.
Next, I considered an inequality to create a bound, but that too was in vain. Next I found out that $lfloor x rfloor = lfloor x/2 rfloor +lfloor x+1/2 rfloor$.
I applied this, but as all were as a sum, it became hard for me to cancel out and it made my work difficult. Now the next problem is about the square root in the box. I once saw in an example that
$$lfloor sqrt{n}+ sqrt{n+1} rfloor = sqrt{4n+1}$$
Now even if this may seem useful, I cannot understand how to remove the $lfloor sqrt{n+1} rfloor $ from the identity. Any help would be helpful!
elementary-number-theory summation floor-function
edited Feb 1 at 13:46
Martin Sleziak
44.8k10119273
$endgroup$
This question already has an answer here:
How to show that $lfloor n/1rfloor+lfloor n/2 rfloor+…+lfloor n/nrfloor+lfloor{sqrt{n}}rfloor$ is even?
1 answer
Let $n$ be a natural number. Prove that
$displaystyle sum_{k=1}^nlfloor n/krfloor+lfloor sqrt{n} rfloor$ is even.
I tried to introduce the fractional part, but it didnt help me.
Next, I considered an inequality to create a bound, but that too was in vain. Next I found out that $lfloor x rfloor = lfloor x/2 rfloor +lfloor x+1/2 rfloor$.
I applied this, but as all were as a sum, it became hard for me to cancel out and it made my work difficult. Now the next problem is about the square root in the box. I once saw in an example that
$$lfloor sqrt{n}+ sqrt{n+1} rfloor = sqrt{4n+1}$$
Now even if this may seem useful, I cannot understand how to remove the $lfloor sqrt{n+1} rfloor $ from the identity. Any help would be helpful!
This question already has an answer here:
How to show that $lfloor n/1rfloor+lfloor n/2 rfloor+…+lfloor n/nrfloor+lfloor{sqrt{n}}rfloor$ is even?
1 answer
elementary-number-theory summation floor-function
elementary-number-theory summation floor-function
edited Feb 1 at 13:46
Martin Sleziak
44.8k10119273
edited Feb 1 at 13:46
Martin Sleziak
44.8k10119273
edited Feb 1 at 13:46
Martin Sleziak
44.8k10119273
edited Feb 1 at 13:46
Martin Sleziak
44.8k10119273
edited Feb 1 at 13:46
Martin Sleziak
44.8k10119273
44.8k10119273
asked Jan 21 at 15:14
user636268
marked as duplicate by rtybase, Community♦ Jan 21 at 15:50
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by rtybase, Community♦ Jan 21 at 15:50
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
$begingroup$
Please format your question through latex.
$endgroup$
– lightxbulb
Jan 21 at 15:17
$begingroup$
I do not know how to use latexx
$endgroup$
– user636268
Jan 21 at 15:20
1
$begingroup$
math.meta.stackexchange.com/questions/5020/…
$endgroup$
– lightxbulb
Jan 21 at 15:20
$begingroup$
Do you mean $lfloor x rfloor$? You did mention largest integer not exceeding $x$.
$endgroup$
– Mohammad Zuhair Khan
Jan 21 at 15:21
$begingroup$
Yes the floor function
$endgroup$
– user636268
Jan 21 at 15:22
add a comment |
2
$begingroup$
Please format your question through latex.
$endgroup$
– lightxbulb
Jan 21 at 15:17
$begingroup$
I do not know how to use latexx
$endgroup$
– user636268
Jan 21 at 15:20
1
$begingroup$
math.meta.stackexchange.com/questions/5020/…
$endgroup$
– lightxbulb
Jan 21 at 15:20
$begingroup$
Do you mean $lfloor x rfloor$? You did mention largest integer not exceeding $x$.
$endgroup$
– Mohammad Zuhair Khan
Jan 21 at 15:21
$begingroup$
Yes the floor function
$endgroup$
– user636268
Jan 21 at 15:22
2
2
$begingroup$
Please format your question through latex.
$endgroup$
– lightxbulb
Jan 21 at 15:17
$begingroup$
Please format your question through latex.
$endgroup$
– lightxbulb
Jan 21 at 15:17
$begingroup$
I do not know how to use latexx
$endgroup$
– user636268
Jan 21 at 15:20
$begingroup$
I do not know how to use latexx
$endgroup$
– user636268
Jan 21 at 15:20
1
1
$begingroup$
math.meta.stackexchange.com/questions/5020/…
$endgroup$
– lightxbulb
Jan 21 at 15:20
$begingroup$
math.meta.stackexchange.com/questions/5020/…
$endgroup$
– lightxbulb
Jan 21 at 15:20
$begingroup$
Do you mean $lfloor x rfloor$? You did mention largest integer not exceeding $x$.
$endgroup$
– Mohammad Zuhair Khan
Jan 21 at 15:21
$begingroup$
Do you mean $lfloor x rfloor$? You did mention largest integer not exceeding $x$.
$endgroup$
– Mohammad Zuhair Khan
Jan 21 at 15:21
$begingroup$
Yes the floor function
$endgroup$
– user636268
Jan 21 at 15:22
$begingroup$
Yes the floor function
$endgroup$
– user636268
Jan 21 at 15:22
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Since $lfloor sqrt{n}rfloor^2$ and $lfloor sqrt{n}rfloor$ have the same parity it suffices to show the following identity
$$sum_{k=1}^nlfloor n/krfloor=2sum_{k=1}^{lfloor sqrt{n}rfloor} lfloor n/krfloor-lfloor sqrt{n}rfloor^2.
$$
See Hurkyl's answer to Simplifying $sum_{i=1}^n{lfloor frac{n}{i} rfloor}$?
In other words, in a direct way,
$$begin{align}
sum_{k=1}^n lfloor n/k rfloor
&= sum_{j,k} [1 leq j] [1 leq k] [jk leq n]\
&=underbrace{sum_{jnot=k} [1 leq j] [1 leq k] [jk leq n]}_{text{even}}+sum_{j=k} [1 leq j] [1 leq k] [jk leq n]\
&equiv sum_{j=k} [1 leq j] [1 leq k] [jk leq n] =lfloor sqrt{n}rfloorpmod{2}end{align}$$
where $[P]$ is $1$ if $P$ is true, and $0$ if false.
answered Jan 21 at 15:31
Robert ZRobert Z
99.8k1068140
$endgroup$
$begingroup$
How do you get that?
$endgroup$
– user636268
Jan 21 at 15:34
1
$begingroup$
This is my hint... ;-)
$endgroup$
– Robert Z
Jan 21 at 15:36
1
$begingroup$
You knew this identity from the beginning?😲
$endgroup$
– user636268
Jan 21 at 15:37
1
$begingroup$
@Md.ShamimAkhtar See my edit.
$endgroup$
– Robert Z
Jan 21 at 15:44
1
$begingroup$
@Md.ShamimAkhtar I gave you a direct way.
$endgroup$
– Robert Z
Jan 21 at 16:06
|
show 3 more comments
$begingroup$
Hint: try to prove this by induction on $n$. When you replace $n$ by $n+1$, some terms in the expression will increase by $1$, count how many do for each $n$.
answered Jan 21 at 15:38
WojowuWojowu
18.8k23172
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Since $lfloor sqrt{n}rfloor^2$ and $lfloor sqrt{n}rfloor$ have the same parity it suffices to show the following identity
$$sum_{k=1}^nlfloor n/krfloor=2sum_{k=1}^{lfloor sqrt{n}rfloor} lfloor n/krfloor-lfloor sqrt{n}rfloor^2.
$$
See Hurkyl's answer to Simplifying $sum_{i=1}^n{lfloor frac{n}{i} rfloor}$?
In other words, in a direct way,
$$begin{align}
sum_{k=1}^n lfloor n/k rfloor
&= sum_{j,k} [1 leq j] [1 leq k] [jk leq n]\
&=underbrace{sum_{jnot=k} [1 leq j] [1 leq k] [jk leq n]}_{text{even}}+sum_{j=k} [1 leq j] [1 leq k] [jk leq n]\
&equiv sum_{j=k} [1 leq j] [1 leq k] [jk leq n] =lfloor sqrt{n}rfloorpmod{2}end{align}$$
where $[P]$ is $1$ if $P$ is true, and $0$ if false.
answered Jan 21 at 15:31
Robert ZRobert Z
99.8k1068140
$endgroup$
$begingroup$
How do you get that?
$endgroup$
– user636268
Jan 21 at 15:34
1
$begingroup$
This is my hint... ;-)
$endgroup$
– Robert Z
Jan 21 at 15:36
1
$begingroup$
You knew this identity from the beginning?😲
$endgroup$
– user636268
Jan 21 at 15:37
1
$begingroup$
@Md.ShamimAkhtar See my edit.
$endgroup$
– Robert Z
Jan 21 at 15:44
1
$begingroup$
@Md.ShamimAkhtar I gave you a direct way.
$endgroup$
– Robert Z
Jan 21 at 16:06
|
show 3 more comments
$begingroup$
Since $lfloor sqrt{n}rfloor^2$ and $lfloor sqrt{n}rfloor$ have the same parity it suffices to show the following identity
$$sum_{k=1}^nlfloor n/krfloor=2sum_{k=1}^{lfloor sqrt{n}rfloor} lfloor n/krfloor-lfloor sqrt{n}rfloor^2.
$$
See Hurkyl's answer to Simplifying $sum_{i=1}^n{lfloor frac{n}{i} rfloor}$?
In other words, in a direct way,
$$begin{align}
sum_{k=1}^n lfloor n/k rfloor
&= sum_{j,k} [1 leq j] [1 leq k] [jk leq n]\
&=underbrace{sum_{jnot=k} [1 leq j] [1 leq k] [jk leq n]}_{text{even}}+sum_{j=k} [1 leq j] [1 leq k] [jk leq n]\
&equiv sum_{j=k} [1 leq j] [1 leq k] [jk leq n] =lfloor sqrt{n}rfloorpmod{2}end{align}$$
where $[P]$ is $1$ if $P$ is true, and $0$ if false.
answered Jan 21 at 15:31
Robert ZRobert Z
99.8k1068140
$endgroup$
$begingroup$
How do you get that?
$endgroup$
– user636268
Jan 21 at 15:34
1
$begingroup$
This is my hint... ;-)
$endgroup$
– Robert Z
Jan 21 at 15:36
1
$begingroup$
You knew this identity from the beginning?😲
$endgroup$
– user636268
Jan 21 at 15:37
1
$begingroup$
@Md.ShamimAkhtar See my edit.
$endgroup$
– Robert Z
Jan 21 at 15:44
1
$begingroup$
@Md.ShamimAkhtar I gave you a direct way.
$endgroup$
– Robert Z
Jan 21 at 16:06
|
show 3 more comments
$begingroup$
Since $lfloor sqrt{n}rfloor^2$ and $lfloor sqrt{n}rfloor$ have the same parity it suffices to show the following identity
$$sum_{k=1}^nlfloor n/krfloor=2sum_{k=1}^{lfloor sqrt{n}rfloor} lfloor n/krfloor-lfloor sqrt{n}rfloor^2.
$$
See Hurkyl's answer to Simplifying $sum_{i=1}^n{lfloor frac{n}{i} rfloor}$?
In other words, in a direct way,
$$begin{align}
sum_{k=1}^n lfloor n/k rfloor
&= sum_{j,k} [1 leq j] [1 leq k] [jk leq n]\
&=underbrace{sum_{jnot=k} [1 leq j] [1 leq k] [jk leq n]}_{text{even}}+sum_{j=k} [1 leq j] [1 leq k] [jk leq n]\
&equiv sum_{j=k} [1 leq j] [1 leq k] [jk leq n] =lfloor sqrt{n}rfloorpmod{2}end{align}$$
where $[P]$ is $1$ if $P$ is true, and $0$ if false.
answered Jan 21 at 15:31
Robert ZRobert Z
99.8k1068140
$endgroup$
Since $lfloor sqrt{n}rfloor^2$ and $lfloor sqrt{n}rfloor$ have the same parity it suffices to show the following identity
$$sum_{k=1}^nlfloor n/krfloor=2sum_{k=1}^{lfloor sqrt{n}rfloor} lfloor n/krfloor-lfloor sqrt{n}rfloor^2.
$$
See Hurkyl's answer to Simplifying $sum_{i=1}^n{lfloor frac{n}{i} rfloor}$?
In other words, in a direct way,
$$begin{align}
sum_{k=1}^n lfloor n/k rfloor
&= sum_{j,k} [1 leq j] [1 leq k] [jk leq n]\
&=underbrace{sum_{jnot=k} [1 leq j] [1 leq k] [jk leq n]}_{text{even}}+sum_{j=k} [1 leq j] [1 leq k] [jk leq n]\
&equiv sum_{j=k} [1 leq j] [1 leq k] [jk leq n] =lfloor sqrt{n}rfloorpmod{2}end{align}$$
where $[P]$ is $1$ if $P$ is true, and $0$ if false.
answered Jan 21 at 15:31
Robert ZRobert Z
99.8k1068140
edited Jan 21 at 16:06
answered Jan 21 at 15:31
Robert ZRobert Z
99.8k1068140
answered Jan 21 at 15:31
Robert ZRobert Z
99.8k1068140
answered Jan 21 at 15:31
Robert ZRobert Z
99.8k1068140
99.8k1068140
$begingroup$
How do you get that?
$endgroup$
– user636268
Jan 21 at 15:34
1
$begingroup$
This is my hint... ;-)
$endgroup$
– Robert Z
Jan 21 at 15:36
1
$begingroup$
You knew this identity from the beginning?😲
$endgroup$
– user636268
Jan 21 at 15:37
1
$begingroup$
@Md.ShamimAkhtar See my edit.
$endgroup$
– Robert Z
Jan 21 at 15:44
1
$begingroup$
@Md.ShamimAkhtar I gave you a direct way.
$endgroup$
– Robert Z
Jan 21 at 16:06
|
show 3 more comments
$begingroup$
How do you get that?
$endgroup$
– user636268
Jan 21 at 15:34
1
$begingroup$
This is my hint... ;-)
$endgroup$
– Robert Z
Jan 21 at 15:36
1
$begingroup$
You knew this identity from the beginning?😲
$endgroup$
– user636268
Jan 21 at 15:37
1
$begingroup$
@Md.ShamimAkhtar See my edit.
$endgroup$
– Robert Z
Jan 21 at 15:44
1
$begingroup$
@Md.ShamimAkhtar I gave you a direct way.
$endgroup$
– Robert Z
Jan 21 at 16:06
$begingroup$
How do you get that?
$endgroup$
– user636268
Jan 21 at 15:34
$begingroup$
How do you get that?
$endgroup$
– user636268
Jan 21 at 15:34
1
1
$begingroup$
This is my hint... ;-)
$endgroup$
– Robert Z
Jan 21 at 15:36
$begingroup$
This is my hint... ;-)
$endgroup$
– Robert Z
Jan 21 at 15:36
1
1
$begingroup$
You knew this identity from the beginning?😲
$endgroup$
– user636268
Jan 21 at 15:37
$begingroup$
You knew this identity from the beginning?😲
$endgroup$
– user636268
Jan 21 at 15:37
1
1
$begingroup$
@Md.ShamimAkhtar See my edit.
$endgroup$
– Robert Z
Jan 21 at 15:44
$begingroup$
@Md.ShamimAkhtar See my edit.
$endgroup$
– Robert Z
Jan 21 at 15:44
1
1
$begingroup$
@Md.ShamimAkhtar I gave you a direct way.
$endgroup$
– Robert Z
Jan 21 at 16:06
$begingroup$
@Md.ShamimAkhtar I gave you a direct way.
$endgroup$
– Robert Z
Jan 21 at 16:06
|
show 3 more comments
$begingroup$
Hint: try to prove this by induction on $n$. When you replace $n$ by $n+1$, some terms in the expression will increase by $1$, count how many do for each $n$.
answered Jan 21 at 15:38
WojowuWojowu
18.8k23172
$endgroup$
add a comment |
$begingroup$
Hint: try to prove this by induction on $n$. When you replace $n$ by $n+1$, some terms in the expression will increase by $1$, count how many do for each $n$.
answered Jan 21 at 15:38
WojowuWojowu
18.8k23172
$endgroup$
add a comment |
$begingroup$
Hint: try to prove this by induction on $n$. When you replace $n$ by $n+1$, some terms in the expression will increase by $1$, count how many do for each $n$.
answered Jan 21 at 15:38
WojowuWojowu
18.8k23172
$endgroup$
Hint: try to prove this by induction on $n$. When you replace $n$ by $n+1$, some terms in the expression will increase by $1$, count how many do for each $n$.
answered Jan 21 at 15:38
WojowuWojowu
18.8k23172
answered Jan 21 at 15:38
WojowuWojowu
18.8k23172
answered Jan 21 at 15:38
WojowuWojowu
18.8k23172
answered Jan 21 at 15:38
WojowuWojowu
18.8k23172
18.8k23172
add a comment |
add a comment |
2
$begingroup$
Please format your question through latex.
$endgroup$
– lightxbulb
Jan 21 at 15:17
$begingroup$
I do not know how to use latexx
$endgroup$
– user636268
Jan 21 at 15:20
1
$begingroup$
math.meta.stackexchange.com/questions/5020/…
$endgroup$
– lightxbulb
Jan 21 at 15:20
$begingroup$
Do you mean $lfloor x rfloor$? You did mention largest integer not exceeding $x$.
$endgroup$
– Mohammad Zuhair Khan
Jan 21 at 15:21
$begingroup$
Yes the floor function
$endgroup$
– user636268
Jan 21 at 15:22