Hint on binomial sum involving roots of unity
$begingroup$
While preparing for an exam, I am currently working on the following task:
Let $n$ be a natural number, and $zeta_n$ a primitive $n$th root of unity. Show that
begin{equation*}
sum_{j=1}^{n} binom{zeta_n^j}{n} = frac{1}{(n-1)!}
end{equation*}
It can be assumed to be known that $sum_{k=1}^{n} zeta_n^k = 1$ for $n=1$ and $sum_{k=1}^{n} zeta_n^k = 0$ otherwise.
I would be grateful for some simple hints for proving this equation. The task was given in a couse on combinatorics, and its solution is obviously somehow related to the Stirling numbers of the first kind. Please do not post the full solution.
combinatorics complex-numbers
asked Jan 21 at 17:36
LlarianLlarian
684
$endgroup$
add a comment |
$begingroup$
While preparing for an exam, I am currently working on the following task:
Let $n$ be a natural number, and $zeta_n$ a primitive $n$th root of unity. Show that
begin{equation*}
sum_{j=1}^{n} binom{zeta_n^j}{n} = frac{1}{(n-1)!}
end{equation*}
It can be assumed to be known that $sum_{k=1}^{n} zeta_n^k = 1$ for $n=1$ and $sum_{k=1}^{n} zeta_n^k = 0$ otherwise.
I would be grateful for some simple hints for proving this equation. The task was given in a couse on combinatorics, and its solution is obviously somehow related to the Stirling numbers of the first kind. Please do not post the full solution.
combinatorics complex-numbers
asked Jan 21 at 17:36
LlarianLlarian
684
$endgroup$
2
$begingroup$
Hint: $dbinom{x}{n} = dfrac{1}{n!} x^n + left(text{a linear combination of } x^i text{ with } 1 leq i < n right) + left(-1right)^n$.
$endgroup$
– darij grinberg
Jan 21 at 17:41
1
$begingroup$
Actually, this has little to do with any combinatorics. Just expand the polynomials in $zeta_n$ and recall that the sum of $zeta_n^{jk}$ for $j=1$ to $n$ is $0$ if $k$ is not divisible by $n$ and $n$ otherwise.
$endgroup$
– Mindlack
Jan 21 at 17:41
1
$begingroup$
The equations that "can be assumed to be known" are slightly insufficient. I suggest instead using $sum_{k=1}^n left(zeta_n^kright)^m = 0$ when $n nmid m$ and $sum_{k=1}^n left(zeta_n^kright)^m = n$ when $n mid m$. (Of course, you can derive these two equations from yours, but they are less misleading.)
$endgroup$
– darij grinberg
Jan 21 at 17:42
$begingroup$
How is $binom{zeta_n^j}{n}$ defined? I'm not familiar with this usage.
$endgroup$
– Robert Lewis
Jan 21 at 17:50
$begingroup$
Thank you for all comments so far. The binomial term was not formally defined, but I assume that $binom{zeta^j_n}{n} = frac{zeta^j_n times (zeta^j_n -1) times dots times (zeta^j_n -n + 1)}{n!}$
$endgroup$
– Llarian
Jan 21 at 17:53
add a comment |
$begingroup$
While preparing for an exam, I am currently working on the following task:
Let $n$ be a natural number, and $zeta_n$ a primitive $n$th root of unity. Show that
begin{equation*}
sum_{j=1}^{n} binom{zeta_n^j}{n} = frac{1}{(n-1)!}
end{equation*}
It can be assumed to be known that $sum_{k=1}^{n} zeta_n^k = 1$ for $n=1$ and $sum_{k=1}^{n} zeta_n^k = 0$ otherwise.
I would be grateful for some simple hints for proving this equation. The task was given in a couse on combinatorics, and its solution is obviously somehow related to the Stirling numbers of the first kind. Please do not post the full solution.
combinatorics complex-numbers
asked Jan 21 at 17:36
LlarianLlarian
684
$endgroup$
While preparing for an exam, I am currently working on the following task:
Let $n$ be a natural number, and $zeta_n$ a primitive $n$th root of unity. Show that
begin{equation*}
sum_{j=1}^{n} binom{zeta_n^j}{n} = frac{1}{(n-1)!}
end{equation*}
It can be assumed to be known that $sum_{k=1}^{n} zeta_n^k = 1$ for $n=1$ and $sum_{k=1}^{n} zeta_n^k = 0$ otherwise.
I would be grateful for some simple hints for proving this equation. The task was given in a couse on combinatorics, and its solution is obviously somehow related to the Stirling numbers of the first kind. Please do not post the full solution.
combinatorics complex-numbers
combinatorics complex-numbers
asked Jan 21 at 17:36
LlarianLlarian
684
asked Jan 21 at 17:36
LlarianLlarian
684
asked Jan 21 at 17:36
LlarianLlarian
684
asked Jan 21 at 17:36
LlarianLlarian
684
asked Jan 21 at 17:36
LlarianLlarian
684
684
2
$begingroup$
Hint: $dbinom{x}{n} = dfrac{1}{n!} x^n + left(text{a linear combination of } x^i text{ with } 1 leq i < n right) + left(-1right)^n$.
$endgroup$
– darij grinberg
Jan 21 at 17:41
1
$begingroup$
Actually, this has little to do with any combinatorics. Just expand the polynomials in $zeta_n$ and recall that the sum of $zeta_n^{jk}$ for $j=1$ to $n$ is $0$ if $k$ is not divisible by $n$ and $n$ otherwise.
$endgroup$
– Mindlack
Jan 21 at 17:41
1
$begingroup$
The equations that "can be assumed to be known" are slightly insufficient. I suggest instead using $sum_{k=1}^n left(zeta_n^kright)^m = 0$ when $n nmid m$ and $sum_{k=1}^n left(zeta_n^kright)^m = n$ when $n mid m$. (Of course, you can derive these two equations from yours, but they are less misleading.)
$endgroup$
– darij grinberg
Jan 21 at 17:42
$begingroup$
How is $binom{zeta_n^j}{n}$ defined? I'm not familiar with this usage.
$endgroup$
– Robert Lewis
Jan 21 at 17:50
$begingroup$
Thank you for all comments so far. The binomial term was not formally defined, but I assume that $binom{zeta^j_n}{n} = frac{zeta^j_n times (zeta^j_n -1) times dots times (zeta^j_n -n + 1)}{n!}$
$endgroup$
– Llarian
Jan 21 at 17:53
add a comment |
2
$begingroup$
Hint: $dbinom{x}{n} = dfrac{1}{n!} x^n + left(text{a linear combination of } x^i text{ with } 1 leq i < n right) + left(-1right)^n$.
$endgroup$
– darij grinberg
Jan 21 at 17:41
1
$begingroup$
Actually, this has little to do with any combinatorics. Just expand the polynomials in $zeta_n$ and recall that the sum of $zeta_n^{jk}$ for $j=1$ to $n$ is $0$ if $k$ is not divisible by $n$ and $n$ otherwise.
$endgroup$
– Mindlack
Jan 21 at 17:41
1
$begingroup$
The equations that "can be assumed to be known" are slightly insufficient. I suggest instead using $sum_{k=1}^n left(zeta_n^kright)^m = 0$ when $n nmid m$ and $sum_{k=1}^n left(zeta_n^kright)^m = n$ when $n mid m$. (Of course, you can derive these two equations from yours, but they are less misleading.)
$endgroup$
– darij grinberg
Jan 21 at 17:42
$begingroup$
How is $binom{zeta_n^j}{n}$ defined? I'm not familiar with this usage.
$endgroup$
– Robert Lewis
Jan 21 at 17:50
$begingroup$
Thank you for all comments so far. The binomial term was not formally defined, but I assume that $binom{zeta^j_n}{n} = frac{zeta^j_n times (zeta^j_n -1) times dots times (zeta^j_n -n + 1)}{n!}$
$endgroup$
– Llarian
Jan 21 at 17:53
2
2
$begingroup$
Hint: $dbinom{x}{n} = dfrac{1}{n!} x^n + left(text{a linear combination of } x^i text{ with } 1 leq i < n right) + left(-1right)^n$.
$endgroup$
– darij grinberg
Jan 21 at 17:41
$begingroup$
Hint: $dbinom{x}{n} = dfrac{1}{n!} x^n + left(text{a linear combination of } x^i text{ with } 1 leq i < n right) + left(-1right)^n$.
$endgroup$
– darij grinberg
Jan 21 at 17:41
1
1
$begingroup$
Actually, this has little to do with any combinatorics. Just expand the polynomials in $zeta_n$ and recall that the sum of $zeta_n^{jk}$ for $j=1$ to $n$ is $0$ if $k$ is not divisible by $n$ and $n$ otherwise.
$endgroup$
– Mindlack
Jan 21 at 17:41
$begingroup$
Actually, this has little to do with any combinatorics. Just expand the polynomials in $zeta_n$ and recall that the sum of $zeta_n^{jk}$ for $j=1$ to $n$ is $0$ if $k$ is not divisible by $n$ and $n$ otherwise.
$endgroup$
– Mindlack
Jan 21 at 17:41
1
1
$begingroup$
The equations that "can be assumed to be known" are slightly insufficient. I suggest instead using $sum_{k=1}^n left(zeta_n^kright)^m = 0$ when $n nmid m$ and $sum_{k=1}^n left(zeta_n^kright)^m = n$ when $n mid m$. (Of course, you can derive these two equations from yours, but they are less misleading.)
$endgroup$
– darij grinberg
Jan 21 at 17:42
$begingroup$
The equations that "can be assumed to be known" are slightly insufficient. I suggest instead using $sum_{k=1}^n left(zeta_n^kright)^m = 0$ when $n nmid m$ and $sum_{k=1}^n left(zeta_n^kright)^m = n$ when $n mid m$. (Of course, you can derive these two equations from yours, but they are less misleading.)
$endgroup$
– darij grinberg
Jan 21 at 17:42
$begingroup$
How is $binom{zeta_n^j}{n}$ defined? I'm not familiar with this usage.
$endgroup$
– Robert Lewis
Jan 21 at 17:50
$begingroup$
How is $binom{zeta_n^j}{n}$ defined? I'm not familiar with this usage.
$endgroup$
– Robert Lewis
Jan 21 at 17:50
$begingroup$
Thank you for all comments so far. The binomial term was not formally defined, but I assume that $binom{zeta^j_n}{n} = frac{zeta^j_n times (zeta^j_n -1) times dots times (zeta^j_n -n + 1)}{n!}$
$endgroup$
– Llarian
Jan 21 at 17:53
$begingroup$
Thank you for all comments so far. The binomial term was not formally defined, but I assume that $binom{zeta^j_n}{n} = frac{zeta^j_n times (zeta^j_n -1) times dots times (zeta^j_n -n + 1)}{n!}$
$endgroup$
– Llarian
Jan 21 at 17:53
add a comment |
0
active
oldest
votes
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%2f3082151%2fhint-on-binomial-sum-involving-roots-of-unity%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3082151%2fhint-on-binomial-sum-involving-roots-of-unity%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
2
$begingroup$
Hint: $dbinom{x}{n} = dfrac{1}{n!} x^n + left(text{a linear combination of } x^i text{ with } 1 leq i < n right) + left(-1right)^n$.
$endgroup$
– darij grinberg
Jan 21 at 17:41
1
$begingroup$
Actually, this has little to do with any combinatorics. Just expand the polynomials in $zeta_n$ and recall that the sum of $zeta_n^{jk}$ for $j=1$ to $n$ is $0$ if $k$ is not divisible by $n$ and $n$ otherwise.
$endgroup$
– Mindlack
Jan 21 at 17:41
1
$begingroup$
The equations that "can be assumed to be known" are slightly insufficient. I suggest instead using $sum_{k=1}^n left(zeta_n^kright)^m = 0$ when $n nmid m$ and $sum_{k=1}^n left(zeta_n^kright)^m = n$ when $n mid m$. (Of course, you can derive these two equations from yours, but they are less misleading.)
$endgroup$
– darij grinberg
Jan 21 at 17:42
$begingroup$
How is $binom{zeta_n^j}{n}$ defined? I'm not familiar with this usage.
$endgroup$
– Robert Lewis
Jan 21 at 17:50
$begingroup$
Thank you for all comments so far. The binomial term was not formally defined, but I assume that $binom{zeta^j_n}{n} = frac{zeta^j_n times (zeta^j_n -1) times dots times (zeta^j_n -n + 1)}{n!}$
$endgroup$
– Llarian
Jan 21 at 17:53