Mixing
Cardinality of set of fractional sums
$begingroup$
What is the cardinality of the set $S_2$:
$$ frac{1}{a_1^n} + frac{1}{a_2^n}, 1 leq a_1,a_2 leq k in N$$
for different values of $n$?
I suspect there is an $n_0$ for which $|S_2| = binom{k+1}{2}, forall n geq n_0$.
Is there such an $n_0$ for all sets $S_m$:
$$ frac{1}{a_1^n} + frac{1}{a_2^n} + cdots + frac{1}{a_m^n}, 1 leq a_i leq k$$
i.e. $n_0: |S_m| = binom{k+m-1}{m}, forall n geq n_0$?
Example:
For the set $S_2$, with $k=3, n=2$:
$$ S = {frac{1}{1} + frac{1}{1}, frac{1}{1}+ frac{1}{2^2}, ldots, frac{1}{3^2} + frac{1}{3^2} } = { 2, frac{5}{4}, frac{10}{9}, frac{1}{2}, frac{13}{36}, frac{2}{9} }$$
so $$ |S_2(k=3,n=2)| = 6 $$
combinatorics elementary-number-theory discrete-mathematics
asked Jan 17 '16 at 0:13
EelvexEelvex
1,156820
$endgroup$
add a comment |
$begingroup$
What is the cardinality of the set $S_2$:
$$ frac{1}{a_1^n} + frac{1}{a_2^n}, 1 leq a_1,a_2 leq k in N$$
for different values of $n$?
I suspect there is an $n_0$ for which $|S_2| = binom{k+1}{2}, forall n geq n_0$.
Is there such an $n_0$ for all sets $S_m$:
$$ frac{1}{a_1^n} + frac{1}{a_2^n} + cdots + frac{1}{a_m^n}, 1 leq a_i leq k$$
i.e. $n_0: |S_m| = binom{k+m-1}{m}, forall n geq n_0$?
Example:
For the set $S_2$, with $k=3, n=2$:
$$ S = {frac{1}{1} + frac{1}{1}, frac{1}{1}+ frac{1}{2^2}, ldots, frac{1}{3^2} + frac{1}{3^2} } = { 2, frac{5}{4}, frac{10}{9}, frac{1}{2}, frac{13}{36}, frac{2}{9} }$$
so $$ |S_2(k=3,n=2)| = 6 $$
combinatorics elementary-number-theory discrete-mathematics
asked Jan 17 '16 at 0:13
EelvexEelvex
1,156820
$endgroup$
1
$begingroup$
I think your question should be tagged [combinatorics] and [elementary-number-theory], not [set-theory] and [cardinals].
$endgroup$
– Hanul Jeon
Jan 17 '16 at 4:58
$begingroup$
A better way to express this would be: is it true that for every $k, m in Bbb{N}$, s.t. $m geq 2$ and $k geq 1$, there is an $n_0 in Bbb{N}$ such that the numbers $$ frac{1}{a_1^n} + dotsb + frac{1}{a_m^n} $$ with $a_1,dotsc,a_m in {1,dotsc,k}$ are all different for every $n geq n_0$?
$endgroup$
– A.P.
Jan 17 '16 at 15:08
1
$begingroup$
By the way, the symbol $S_n$ is less than ideal, because your set depends on $k$ and $n$, too. Thus a symbol like $S_2(k,n)$ or $S_{2,k}(n)$ would be more appropriate. This is made even more important by the fact that you're asking about a property of this set in function of $n$.
$endgroup$
– A.P.
Jan 17 '16 at 15:48
$begingroup$
I'm sorry: I can't edit it anymore, but in my previous comment I should have said "with $1 leq a_1 leq dotsc leq a_n leq k$".
$endgroup$
– A.P.
Jan 17 '16 at 16:01
$begingroup$
@A.P. thanks for your comments. I'm also interested in the cardinality of the set, not just a proof of existence of $n_0$. I used $S_x$ instead of $S_{m,k,n}$ (or whatever) to remove some clutter.
$endgroup$
– Eelvex
Jan 17 '16 at 20:14
add a comment |
$begingroup$
What is the cardinality of the set $S_2$:
$$ frac{1}{a_1^n} + frac{1}{a_2^n}, 1 leq a_1,a_2 leq k in N$$
for different values of $n$?
I suspect there is an $n_0$ for which $|S_2| = binom{k+1}{2}, forall n geq n_0$.
Is there such an $n_0$ for all sets $S_m$:
$$ frac{1}{a_1^n} + frac{1}{a_2^n} + cdots + frac{1}{a_m^n}, 1 leq a_i leq k$$
i.e. $n_0: |S_m| = binom{k+m-1}{m}, forall n geq n_0$?
Example:
For the set $S_2$, with $k=3, n=2$:
$$ S = {frac{1}{1} + frac{1}{1}, frac{1}{1}+ frac{1}{2^2}, ldots, frac{1}{3^2} + frac{1}{3^2} } = { 2, frac{5}{4}, frac{10}{9}, frac{1}{2}, frac{13}{36}, frac{2}{9} }$$
so $$ |S_2(k=3,n=2)| = 6 $$
combinatorics elementary-number-theory discrete-mathematics
asked Jan 17 '16 at 0:13
EelvexEelvex
1,156820
$endgroup$
What is the cardinality of the set $S_2$:
$$ frac{1}{a_1^n} + frac{1}{a_2^n}, 1 leq a_1,a_2 leq k in N$$
for different values of $n$?
I suspect there is an $n_0$ for which $|S_2| = binom{k+1}{2}, forall n geq n_0$.
Is there such an $n_0$ for all sets $S_m$:
$$ frac{1}{a_1^n} + frac{1}{a_2^n} + cdots + frac{1}{a_m^n}, 1 leq a_i leq k$$
i.e. $n_0: |S_m| = binom{k+m-1}{m}, forall n geq n_0$?
Example:
For the set $S_2$, with $k=3, n=2$:
$$ S = {frac{1}{1} + frac{1}{1}, frac{1}{1}+ frac{1}{2^2}, ldots, frac{1}{3^2} + frac{1}{3^2} } = { 2, frac{5}{4}, frac{10}{9}, frac{1}{2}, frac{13}{36}, frac{2}{9} }$$
so $$ |S_2(k=3,n=2)| = 6 $$
combinatorics elementary-number-theory discrete-mathematics
combinatorics elementary-number-theory discrete-mathematics
asked Jan 17 '16 at 0:13
EelvexEelvex
1,156820
asked Jan 17 '16 at 0:13
EelvexEelvex
1,156820
edited Jan 17 '16 at 14:16
Eelvex
asked Jan 17 '16 at 0:13
EelvexEelvex
1,156820
asked Jan 17 '16 at 0:13
EelvexEelvex
1,156820
asked Jan 17 '16 at 0:13
EelvexEelvex
1,156820
1,156820
1
$begingroup$
I think your question should be tagged [combinatorics] and [elementary-number-theory], not [set-theory] and [cardinals].
$endgroup$
– Hanul Jeon
Jan 17 '16 at 4:58
$begingroup$
A better way to express this would be: is it true that for every $k, m in Bbb{N}$, s.t. $m geq 2$ and $k geq 1$, there is an $n_0 in Bbb{N}$ such that the numbers $$ frac{1}{a_1^n} + dotsb + frac{1}{a_m^n} $$ with $a_1,dotsc,a_m in {1,dotsc,k}$ are all different for every $n geq n_0$?
$endgroup$
– A.P.
Jan 17 '16 at 15:08
1
$begingroup$
By the way, the symbol $S_n$ is less than ideal, because your set depends on $k$ and $n$, too. Thus a symbol like $S_2(k,n)$ or $S_{2,k}(n)$ would be more appropriate. This is made even more important by the fact that you're asking about a property of this set in function of $n$.
$endgroup$
– A.P.
Jan 17 '16 at 15:48
$begingroup$
I'm sorry: I can't edit it anymore, but in my previous comment I should have said "with $1 leq a_1 leq dotsc leq a_n leq k$".
$endgroup$
– A.P.
Jan 17 '16 at 16:01
$begingroup$
@A.P. thanks for your comments. I'm also interested in the cardinality of the set, not just a proof of existence of $n_0$. I used $S_x$ instead of $S_{m,k,n}$ (or whatever) to remove some clutter.
$endgroup$
– Eelvex
Jan 17 '16 at 20:14
add a comment |
1
$begingroup$
I think your question should be tagged [combinatorics] and [elementary-number-theory], not [set-theory] and [cardinals].
$endgroup$
– Hanul Jeon
Jan 17 '16 at 4:58
$begingroup$
A better way to express this would be: is it true that for every $k, m in Bbb{N}$, s.t. $m geq 2$ and $k geq 1$, there is an $n_0 in Bbb{N}$ such that the numbers $$ frac{1}{a_1^n} + dotsb + frac{1}{a_m^n} $$ with $a_1,dotsc,a_m in {1,dotsc,k}$ are all different for every $n geq n_0$?
$endgroup$
– A.P.
Jan 17 '16 at 15:08
1
$begingroup$
By the way, the symbol $S_n$ is less than ideal, because your set depends on $k$ and $n$, too. Thus a symbol like $S_2(k,n)$ or $S_{2,k}(n)$ would be more appropriate. This is made even more important by the fact that you're asking about a property of this set in function of $n$.
$endgroup$
– A.P.
Jan 17 '16 at 15:48
$begingroup$
I'm sorry: I can't edit it anymore, but in my previous comment I should have said "with $1 leq a_1 leq dotsc leq a_n leq k$".
$endgroup$
– A.P.
Jan 17 '16 at 16:01
$begingroup$
@A.P. thanks for your comments. I'm also interested in the cardinality of the set, not just a proof of existence of $n_0$. I used $S_x$ instead of $S_{m,k,n}$ (or whatever) to remove some clutter.
$endgroup$
– Eelvex
Jan 17 '16 at 20:14
1
1
$begingroup$
I think your question should be tagged [combinatorics] and [elementary-number-theory], not [set-theory] and [cardinals].
$endgroup$
– Hanul Jeon
Jan 17 '16 at 4:58
$begingroup$
I think your question should be tagged [combinatorics] and [elementary-number-theory], not [set-theory] and [cardinals].
$endgroup$
– Hanul Jeon
Jan 17 '16 at 4:58
$begingroup$
A better way to express this would be: is it true that for every $k, m in Bbb{N}$, s.t. $m geq 2$ and $k geq 1$, there is an $n_0 in Bbb{N}$ such that the numbers $$ frac{1}{a_1^n} + dotsb + frac{1}{a_m^n} $$ with $a_1,dotsc,a_m in {1,dotsc,k}$ are all different for every $n geq n_0$?
$endgroup$
– A.P.
Jan 17 '16 at 15:08
$begingroup$
A better way to express this would be: is it true that for every $k, m in Bbb{N}$, s.t. $m geq 2$ and $k geq 1$, there is an $n_0 in Bbb{N}$ such that the numbers $$ frac{1}{a_1^n} + dotsb + frac{1}{a_m^n} $$ with $a_1,dotsc,a_m in {1,dotsc,k}$ are all different for every $n geq n_0$?
$endgroup$
– A.P.
Jan 17 '16 at 15:08
1
1
$begingroup$
By the way, the symbol $S_n$ is less than ideal, because your set depends on $k$ and $n$, too. Thus a symbol like $S_2(k,n)$ or $S_{2,k}(n)$ would be more appropriate. This is made even more important by the fact that you're asking about a property of this set in function of $n$.
$endgroup$
– A.P.
Jan 17 '16 at 15:48
$begingroup$
By the way, the symbol $S_n$ is less than ideal, because your set depends on $k$ and $n$, too. Thus a symbol like $S_2(k,n)$ or $S_{2,k}(n)$ would be more appropriate. This is made even more important by the fact that you're asking about a property of this set in function of $n$.
$endgroup$
– A.P.
Jan 17 '16 at 15:48
$begingroup$
I'm sorry: I can't edit it anymore, but in my previous comment I should have said "with $1 leq a_1 leq dotsc leq a_n leq k$".
$endgroup$
– A.P.
Jan 17 '16 at 16:01
$begingroup$
I'm sorry: I can't edit it anymore, but in my previous comment I should have said "with $1 leq a_1 leq dotsc leq a_n leq k$".
$endgroup$
– A.P.
Jan 17 '16 at 16:01
$begingroup$
@A.P. thanks for your comments. I'm also interested in the cardinality of the set, not just a proof of existence of $n_0$. I used $S_x$ instead of $S_{m,k,n}$ (or whatever) to remove some clutter.
$endgroup$
– Eelvex
Jan 17 '16 at 20:14
$begingroup$
@A.P. thanks for your comments. I'm also interested in the cardinality of the set, not just a proof of existence of $n_0$. I used $S_x$ instead of $S_{m,k,n}$ (or whatever) to remove some clutter.
$endgroup$
– Eelvex
Jan 17 '16 at 20:14
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Proposition. For each $m, kge 2$, $|S_m(k,n)|={k+m-1choose m}$ for each $nge log_{frac k{k-1}} m-1$.
Proof. We shall follow A.P.’s comment. Let $mathcal S$ be a family of non-decreasing sequences $(a_1,dots, a_m)$ of natural numbers between $1$ and $k$. For each $S=(a_1,dots, a_m)in mathcal S$ put $Sigma S=a_1^{-n}+dots a_m^{-n}$. Since $|mathcal S|={k+m-1choose m}$, we have to show that numbers $Sigma S$ are distinct when $Sinmathcal S$. Suppose to the contrary, that there exists distinct sequences $S=(a_1,dots, a_m)$ and $T=(b_1,dots, b_m)$ in $mathcal S$ such that $Sigma S=Sigma T$. Let $i$ be the smallest number such that $a_ine b_i$. Without loss of generality we may suppose that $a_i<b_i$. Then
$$Sigma S-Sigma Tge a^{-n}_i- b^{-n}_i+sum_{j>i} a^{-n}_j - b^{-n}_jge$$ $$a^{-n}_i- b^{-n}_i+sum_{j>i} k^{-n} - b^{-n}_i=$$ $$a^{-n}_i+(m-i)k^{-n}-(m-i+1)b^{-n}_ige$$ $$ a^{-n}_i+(m-i)k^{-n}-(m-i+1)(a_i+1)^{-n}ge$$ $$ a^{-n}_i+(m-1)k^{-n}-m(a_i+1)^{-n}=f(a_i),$$
where $f(x)=x^{-n}+(m-1)k^{-n}-m(x+1)^{-n}$. Since $f(k-1)=(k-1)^{-n}-k^{-n}>0$, to obtain a contradiction it suffices to show that
$f’(x)<0$ for $1le x<k-1$. Since $f’(x)=(-n)x^{-n-1}+nm(x+1)^{-n-1}$, we have to check that
$x^{-n-1}-m(x+1)^{-n-1}>0$
$x^{-n-1}>m(x+1)^{-n-1}$
$left( x+frac{1}{x}right)^{n+1}>m$
which is true, because $left(x+frac{1}{x}right)^{n+1}>left(1+frac{1}{k-1}right)^{n+1}ge m$. $square$
answered Jan 10 at 4:28
Alex RavskyAlex Ravsky
40.5k32282
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1615044%2fcardinality-of-set-of-fractional-sums%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Proposition. For each $m, kge 2$, $|S_m(k,n)|={k+m-1choose m}$ for each $nge log_{frac k{k-1}} m-1$.
Proof. We shall follow A.P.’s comment. Let $mathcal S$ be a family of non-decreasing sequences $(a_1,dots, a_m)$ of natural numbers between $1$ and $k$. For each $S=(a_1,dots, a_m)in mathcal S$ put $Sigma S=a_1^{-n}+dots a_m^{-n}$. Since $|mathcal S|={k+m-1choose m}$, we have to show that numbers $Sigma S$ are distinct when $Sinmathcal S$. Suppose to the contrary, that there exists distinct sequences $S=(a_1,dots, a_m)$ and $T=(b_1,dots, b_m)$ in $mathcal S$ such that $Sigma S=Sigma T$. Let $i$ be the smallest number such that $a_ine b_i$. Without loss of generality we may suppose that $a_i<b_i$. Then
$$Sigma S-Sigma Tge a^{-n}_i- b^{-n}_i+sum_{j>i} a^{-n}_j - b^{-n}_jge$$ $$a^{-n}_i- b^{-n}_i+sum_{j>i} k^{-n} - b^{-n}_i=$$ $$a^{-n}_i+(m-i)k^{-n}-(m-i+1)b^{-n}_ige$$ $$ a^{-n}_i+(m-i)k^{-n}-(m-i+1)(a_i+1)^{-n}ge$$ $$ a^{-n}_i+(m-1)k^{-n}-m(a_i+1)^{-n}=f(a_i),$$
where $f(x)=x^{-n}+(m-1)k^{-n}-m(x+1)^{-n}$. Since $f(k-1)=(k-1)^{-n}-k^{-n}>0$, to obtain a contradiction it suffices to show that
$f’(x)<0$ for $1le x<k-1$. Since $f’(x)=(-n)x^{-n-1}+nm(x+1)^{-n-1}$, we have to check that
$x^{-n-1}-m(x+1)^{-n-1}>0$
$x^{-n-1}>m(x+1)^{-n-1}$
$left( x+frac{1}{x}right)^{n+1}>m$
which is true, because $left(x+frac{1}{x}right)^{n+1}>left(1+frac{1}{k-1}right)^{n+1}ge m$. $square$
answered Jan 10 at 4:28
Alex RavskyAlex Ravsky
40.5k32282
$endgroup$
add a comment |
$begingroup$
Proposition. For each $m, kge 2$, $|S_m(k,n)|={k+m-1choose m}$ for each $nge log_{frac k{k-1}} m-1$.
Proof. We shall follow A.P.’s comment. Let $mathcal S$ be a family of non-decreasing sequences $(a_1,dots, a_m)$ of natural numbers between $1$ and $k$. For each $S=(a_1,dots, a_m)in mathcal S$ put $Sigma S=a_1^{-n}+dots a_m^{-n}$. Since $|mathcal S|={k+m-1choose m}$, we have to show that numbers $Sigma S$ are distinct when $Sinmathcal S$. Suppose to the contrary, that there exists distinct sequences $S=(a_1,dots, a_m)$ and $T=(b_1,dots, b_m)$ in $mathcal S$ such that $Sigma S=Sigma T$. Let $i$ be the smallest number such that $a_ine b_i$. Without loss of generality we may suppose that $a_i<b_i$. Then
$$Sigma S-Sigma Tge a^{-n}_i- b^{-n}_i+sum_{j>i} a^{-n}_j - b^{-n}_jge$$ $$a^{-n}_i- b^{-n}_i+sum_{j>i} k^{-n} - b^{-n}_i=$$ $$a^{-n}_i+(m-i)k^{-n}-(m-i+1)b^{-n}_ige$$ $$ a^{-n}_i+(m-i)k^{-n}-(m-i+1)(a_i+1)^{-n}ge$$ $$ a^{-n}_i+(m-1)k^{-n}-m(a_i+1)^{-n}=f(a_i),$$
where $f(x)=x^{-n}+(m-1)k^{-n}-m(x+1)^{-n}$. Since $f(k-1)=(k-1)^{-n}-k^{-n}>0$, to obtain a contradiction it suffices to show that
$f’(x)<0$ for $1le x<k-1$. Since $f’(x)=(-n)x^{-n-1}+nm(x+1)^{-n-1}$, we have to check that
$x^{-n-1}-m(x+1)^{-n-1}>0$
$x^{-n-1}>m(x+1)^{-n-1}$
$left( x+frac{1}{x}right)^{n+1}>m$
which is true, because $left(x+frac{1}{x}right)^{n+1}>left(1+frac{1}{k-1}right)^{n+1}ge m$. $square$
answered Jan 10 at 4:28
Alex RavskyAlex Ravsky
40.5k32282
$endgroup$
add a comment |
$begingroup$
Proposition. For each $m, kge 2$, $|S_m(k,n)|={k+m-1choose m}$ for each $nge log_{frac k{k-1}} m-1$.
Proof. We shall follow A.P.’s comment. Let $mathcal S$ be a family of non-decreasing sequences $(a_1,dots, a_m)$ of natural numbers between $1$ and $k$. For each $S=(a_1,dots, a_m)in mathcal S$ put $Sigma S=a_1^{-n}+dots a_m^{-n}$. Since $|mathcal S|={k+m-1choose m}$, we have to show that numbers $Sigma S$ are distinct when $Sinmathcal S$. Suppose to the contrary, that there exists distinct sequences $S=(a_1,dots, a_m)$ and $T=(b_1,dots, b_m)$ in $mathcal S$ such that $Sigma S=Sigma T$. Let $i$ be the smallest number such that $a_ine b_i$. Without loss of generality we may suppose that $a_i<b_i$. Then
$$Sigma S-Sigma Tge a^{-n}_i- b^{-n}_i+sum_{j>i} a^{-n}_j - b^{-n}_jge$$ $$a^{-n}_i- b^{-n}_i+sum_{j>i} k^{-n} - b^{-n}_i=$$ $$a^{-n}_i+(m-i)k^{-n}-(m-i+1)b^{-n}_ige$$ $$ a^{-n}_i+(m-i)k^{-n}-(m-i+1)(a_i+1)^{-n}ge$$ $$ a^{-n}_i+(m-1)k^{-n}-m(a_i+1)^{-n}=f(a_i),$$
where $f(x)=x^{-n}+(m-1)k^{-n}-m(x+1)^{-n}$. Since $f(k-1)=(k-1)^{-n}-k^{-n}>0$, to obtain a contradiction it suffices to show that
$f’(x)<0$ for $1le x<k-1$. Since $f’(x)=(-n)x^{-n-1}+nm(x+1)^{-n-1}$, we have to check that
$x^{-n-1}-m(x+1)^{-n-1}>0$
$x^{-n-1}>m(x+1)^{-n-1}$
$left( x+frac{1}{x}right)^{n+1}>m$
which is true, because $left(x+frac{1}{x}right)^{n+1}>left(1+frac{1}{k-1}right)^{n+1}ge m$. $square$
answered Jan 10 at 4:28
Alex RavskyAlex Ravsky
40.5k32282
$endgroup$
Proposition. For each $m, kge 2$, $|S_m(k,n)|={k+m-1choose m}$ for each $nge log_{frac k{k-1}} m-1$.
Proof. We shall follow A.P.’s comment. Let $mathcal S$ be a family of non-decreasing sequences $(a_1,dots, a_m)$ of natural numbers between $1$ and $k$. For each $S=(a_1,dots, a_m)in mathcal S$ put $Sigma S=a_1^{-n}+dots a_m^{-n}$. Since $|mathcal S|={k+m-1choose m}$, we have to show that numbers $Sigma S$ are distinct when $Sinmathcal S$. Suppose to the contrary, that there exists distinct sequences $S=(a_1,dots, a_m)$ and $T=(b_1,dots, b_m)$ in $mathcal S$ such that $Sigma S=Sigma T$. Let $i$ be the smallest number such that $a_ine b_i$. Without loss of generality we may suppose that $a_i<b_i$. Then
$$Sigma S-Sigma Tge a^{-n}_i- b^{-n}_i+sum_{j>i} a^{-n}_j - b^{-n}_jge$$ $$a^{-n}_i- b^{-n}_i+sum_{j>i} k^{-n} - b^{-n}_i=$$ $$a^{-n}_i+(m-i)k^{-n}-(m-i+1)b^{-n}_ige$$ $$ a^{-n}_i+(m-i)k^{-n}-(m-i+1)(a_i+1)^{-n}ge$$ $$ a^{-n}_i+(m-1)k^{-n}-m(a_i+1)^{-n}=f(a_i),$$
where $f(x)=x^{-n}+(m-1)k^{-n}-m(x+1)^{-n}$. Since $f(k-1)=(k-1)^{-n}-k^{-n}>0$, to obtain a contradiction it suffices to show that
$f’(x)<0$ for $1le x<k-1$. Since $f’(x)=(-n)x^{-n-1}+nm(x+1)^{-n-1}$, we have to check that
$x^{-n-1}-m(x+1)^{-n-1}>0$
$x^{-n-1}>m(x+1)^{-n-1}$
$left( x+frac{1}{x}right)^{n+1}>m$
which is true, because $left(x+frac{1}{x}right)^{n+1}>left(1+frac{1}{k-1}right)^{n+1}ge m$. $square$
answered Jan 10 at 4:28
Alex RavskyAlex Ravsky
40.5k32282
answered Jan 10 at 4:28
Alex RavskyAlex Ravsky
40.5k32282
answered Jan 10 at 4:28
Alex RavskyAlex Ravsky
40.5k32282
answered Jan 10 at 4:28
Alex RavskyAlex Ravsky
40.5k32282
40.5k32282
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1615044%2fcardinality-of-set-of-fractional-sums%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
I think your question should be tagged [combinatorics] and [elementary-number-theory], not [set-theory] and [cardinals].
$endgroup$
– Hanul Jeon
Jan 17 '16 at 4:58
$begingroup$
A better way to express this would be: is it true that for every $k, m in Bbb{N}$, s.t. $m geq 2$ and $k geq 1$, there is an $n_0 in Bbb{N}$ such that the numbers $$ frac{1}{a_1^n} + dotsb + frac{1}{a_m^n} $$ with $a_1,dotsc,a_m in {1,dotsc,k}$ are all different for every $n geq n_0$?
$endgroup$
– A.P.
Jan 17 '16 at 15:08
1
$begingroup$
By the way, the symbol $S_n$ is less than ideal, because your set depends on $k$ and $n$, too. Thus a symbol like $S_2(k,n)$ or $S_{2,k}(n)$ would be more appropriate. This is made even more important by the fact that you're asking about a property of this set in function of $n$.
$endgroup$
– A.P.
Jan 17 '16 at 15:48
$begingroup$
I'm sorry: I can't edit it anymore, but in my previous comment I should have said "with $1 leq a_1 leq dotsc leq a_n leq k$".
$endgroup$
– A.P.
Jan 17 '16 at 16:01
$begingroup$
@A.P. thanks for your comments. I'm also interested in the cardinality of the set, not just a proof of existence of $n_0$. I used $S_x$ instead of $S_{m,k,n}$ (or whatever) to remove some clutter.
$endgroup$
– Eelvex
Jan 17 '16 at 20:14