Tag Info

Hot answers tagged

7

Given $n>2$. So for every integer $x$ such that $1<x<(n+1),$ we have $x|n!$ and $x\not|(n!-1).$ $\therefore$ either $(n!-1)$ is a prime, or $\exists$ a prime $p\ge (n+1) $ such that $p|(n!-1)$. So in any case, $\exists$ a prime $p$ such that $(n+1)\le p\le (n!-1)$.


5

For $n=2$ take $p=2$. For $n\geq 3$, take $p$ as a prime divisor of $n!-1$ (hence $p<n!$). Then $p>n$, if not, $p$ divide $n!$, hence divide $n!-(n!-1)=1$.


5

Since $7$ is a factor of $\frac{12!}{r!(12-r)!}=924$, $r!$ and $(12-r)!$ must not have factor $7$, which implies $r=6$.


5

Wilson's theorem says that for a prime $p$ we have $(p-1)! \equiv -1 \pmod{p}$. It follows that $(p-2)! \equiv 1 \pmod{p}$, and hence $(p-2)! - 1$ is composite for every prime $p > 5$, since then $(p-2)! - 1 > p$. Since there are arbitrarily large primes, the proposition follows.


4

The keyword here is derangements. The formula for the number of derangements of $n$ things is a bit messy: $$d_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\;.$$ You’ll find some other formulas, less easy to prove but more usable, at the link; perhaps the nicest is $$d_n=\left\lfloor\frac{n!}e+\frac12\right\rfloor\;,$$ for $n\ge 1$.


4

$$\frac{n!}{(n-k)!(k-2)!}=n(n-1)\frac{(n-2)!}{\{n-2-(k-2)\}!\cdot(k-2)!}=n(n-1)\binom{n-2}{k-2}$$ $$\sum_{k=2}^n\frac{n!}{(n-k)!(k-2)!}=n(n-1)\sum_{k=2}^n\binom{n-2}{k-2}$$ Now set $k-2=r$ to get $$\sum_{k=2}^n\binom{n-2}{k-2}=\sum_{r=0}^{n-2}\binom{n-2}r=(1+1)^{n-2}$$


4

First note that $$\frac{(2n)!^2i!j!}{n!^2(2i)!(2j)!}=\frac{n!\binom{2n}n}{i!\binom{2i}i}\cdot\frac{n!\binom{2n}n}{j!\binom{2j}j}\;,\tag{1}$$ so we need only show that each of the factors on the righthand side of $(1)$ is an integer. For any $k$, $k!\binom{2k}k$ is the number of ways of selecting $k$ of the members of the set $\{1,2,\ldots,2k\}$ and ...


4

$$\begin{align*} (-4)^n\binom{-1/2}n&=(-4)^n\frac{(-1/2)^{\underline n}}{n!}\\\\ &=\frac{(-4)^n}{n!}\left(-\frac12\right)\left(-\frac32\right)\ldots\left(-\frac{2n-1}2\right)\\\\ &=\frac{(-4)^n}{n!}\cdot\frac{(2n-1)!!}{(-2)^n}\\\\ &=\frac{2^nn!(2n-1)!!}{(n!)^2}\\\\ &=\frac{(2n)!!(2n-1)!!}{(n!)^2}\\\\ &=\frac{(2n)!}{(n!)^2}\\\\ ...


3

Are you familiar with Gegenbauer polynomials ? Either way, we can use their definition to rewrite the sum as $a_n=\pi\cdot\big(-{\bf i}\big)^n\cdot{\large\bf C}_n^{(d)}\bigg(\dfrac{\bf i}2\bigg)\cdot\displaystyle\lim_{\delta\to d}\dfrac{\csc\big(\delta\pi\big)}{\big(-\delta\big)!}$ , where the limit can be evaluated using Euler's reflection formula for ...


3

You have not specified what is meant by the definition of the generalized binomial coefficient. We take one interpretation, which may not be the intended one. The term $\binom{-1/2}{n}$ is equal to $$\frac{1}{n!}\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right)\cdots \left(-\frac{2n-1}{2}\right).$$ Multiply the top by $(2)(4)\cdots (2n)$ and the bottom by ...


3

The base case trivial, so assume it holds for $n-1$, i.e. $(n-1)!\le e(n-1)\left(\frac{n-1}e\right)^{\!n-1}$. Then \begin{align*}n!&=n\cdot(n-1)!\le n\cdot e(n-1)\left(\frac{n-1}e\right)^{\!n-1}=ne\cdot(n-1)\frac{(n-1)^{n-1}}{e^{n-1}}\\&=ne\cdot\frac{(n-1)^n}{e^{n-1}}=ne\cdot\frac{(n-1)^n}{e^n}\cdot e=ne\cdot\frac{(n-1)^n\cdot n^n}{e^n\cdot n^n}\cdot ...


3

You can use Stirling's formula: $x! \sim \sqrt{2\pi x} (x/e)^x$. In your case, assuming $a > 0$ you get $$ \frac{(x!)^n}{(ax)!} \sim (2\pi)^{(n-1)/2} \frac{x^{nx}}{e^{nx}} \frac{e^{ax}}{(ax)^{ax}} = (2\pi)^{(n-1)/2} \frac{(x/e)^{(n-a)x}}{a^{ax}}. $$ If $a \geq n$ and $a > 1$ then this tends to zero. If $n > a$ then it tends to infinity. This leaves ...


3

First lets define $f(n)$ to be equal to the product of the first n positive odd integers. We have $f(n)=\frac{(2n)!}{2^n (n)!}$ (explanation here). Logically, if $n \geq a$, then $\frac{f(n)}{f(a)}$ is an integer because all of the terms of $f(a)$ exist in $f(n)$. Since $f(n)=\frac{(2n)!}{2^n (n)!}$, we also have $\frac{(2n)!}{(n)!}=2^n f(n)$ and likewise ...


3

Suppose that $a\ge n$ is an integer. For $k\in[n]$ let $A_k$ be the set of functions from $[n]$ to $[a]$ that do not have $k$ in their ranges. Then by a straightforward inclusion-exclusion argument $$\sum_{k=0}^n(-1)^k\binom{n}k(a-k)^n\tag{1}$$ is the number of functions from $[n]$ to $[a]$ whose ranges include (and therefore are equal to) $[n]$. This, of ...


3

More generally if $p$ is any polynomial function of degree (at most)$~n$ with coefficient $c$ in degree$~n$, one has $$ \sum_{k=0}^n(-1)^k\binom nk p(x-k) = cn!, $$ independently of $x$. This applies here for $p:x\mapsto x^n$ with $c=1$. It easily follows by induction, given that $$ \sum_{k=0}^n(-1)^k\binom nk p(x-k) = \sum_{k=0}^{n-1}\binom{n-1}k ...


3

Use your induction hypothesis and $n+1>2$.


3

The number of trailing zeros on $n!$ is just the number of factors of 5 lurking in $\{1, 2, .... n\}$, which is $$\sum_{n\ge 1} \left\lfloor{n\over 5^n}\right\rfloor.$$


3

First of all, the actual wording has only one free variable: $$(n+1)! -1+(n+1)\cdot(n+1)! = -1 + (n+1)!\cdot(1+n+1) = (n+2)! - 1$$ All that is used are the usual distributive law, note that $(n+1)!$ is an integer just like any other and the $!$ just binds the immediately preceeding integer, and the equation $$n! = n \cdot (n-1)!$$ Here is the same with some ...


2

Derivation of the Series The Binomial Theorem says that $$ \begin{align} (1-x)^{-1/2} &=1+\frac{(-\frac12)}{1}(-x)^1+\frac{(-\frac12)(-\frac32)}{1\cdot2}(-x)^2+\frac{(-\frac12)(-\frac32)(-\frac52)}{1\cdot2\cdot3}(-x)^3+\dots\\ ...


2

The equation $$ \sum_{i = 0}^{n}\sum_{j = 0}^{n} (-1)^{i + j} \binom{n}{i} \binom{n}{j} \frac{2^{2n}(P(n))^{2}P(i + j)}{2^{i+j}P(i)P(j)} = P(2n) $$ is a prime suspect for combinatorial proof (combinatorial proof). The idea would be to find a quantity that both sides are counting. Particularly, the quantity $\binom{n}{i}\binom{n}{j}$ is what suggests the ...


2

Try to prove first that $$n\cdot 1 + (n-1)\cdot 2 + \dots + 2\cdot (n-1) + 1\cdot n = \frac{n(n+1)(n+2)}6.$$ (I have posted a separate question about this sum.) Then use the AM-GM inequality for the sum on the LHS.


2

You can use a combinatorial argument. How many groups of size $k$ can be formed from $k$ students? There are $n$ options for the first student, $n-1$ options for the second $\dots (n-k+1)$ options for the $k$'th student. Therefore there are $n\cdot (n-1)\cdot\dots (n-k+1)=\frac{n!}{(n-k)!}$ possible groups. However we have overcounted! Because in a group of ...


2

Hint: $(n+1)! = (n+1) \cdot n! \geq (n+1) \cdot 2^{n-1} \geq 2 \cdot 2^{n-1} = 2^{(n +1) -1}.$


2

You could use AM-GM inequality. You get: $$\sqrt[n]{n!} = \sqrt{1\cdot2\cdots n} \le \frac{1+2+\dots+n}n=\frac{n+1}2$$ which means $$0\le \frac{\sqrt[n]{n!}}{n^2} \le \frac{n+1}{2n^2}$$ and thus $$\lim_{n\to\infty} \frac{\sqrt[n]{n!}}{n^2}=0.$$


2

You could just use the straight-forward ratio test: $$ a_{n+1}/a_n = \frac{(n+2)! (n+2)^n n^{2n}}{(n+1)! (n+1)^{n-1} (n+1)^{2n+2}} = \left(\frac{n+2}{n+1}\right)^{n+1} \left(\frac{n}{n+1}\right)^{2n} $$ Since $\left(\frac{n+2}{n+1}\right)^{n+1} = \left(1+\frac{1}{n+1}\right)^{n+1} \to \mathrm{e}$ and $\left(\frac{n}{n+1}\right)^n = ...


2

Use the definition $$_nC_r = \frac{n!}{r!(n-r)!}$$ Plug in $n=12$ and set everything equal to $924$. With a little algebra you'll get $$\frac{12!}{924} = r!(12-r)!$$ Then write $924 = 2^2\cdot 3 \cdot 7 \cdot 11$ which means $$\frac{12!}{924} =\require{cancel} \frac{1\cdot 2\cdot \cancel{3} \cdot \cancel{4} \cdot 5 \cdot 6 \cdot \cancel{7} \cdot 8 \cdot 9 ...


2

This is not possible because the expression does not only depend on $r$ and $n$. For example, take $n=5$, $i=2$, $j=2$, to get $6\cdot 6\cdot 24\cdot 24=20736$, then take $i=1$, $j=3$ to get $24\cdot 2\cdot 2\cdot 720=69120$ from the same expression, even though $n$ and $r$ are the same.


2

I don't know of a quick way. As $12-r$ is a solution whenever $r$ is, you can concentrate on $r \le \frac {12}2$ For reasonably small values, you can then do binary search. If the value $12$ is larger, you can use Stirling's approximation $12Cr=\frac {12!}{r!(12-r)!}\approx\frac {12^{12}\sqrt{24\pi}}{r^r(12-r)^{12-r}2\pi\sqrt{r(12-r)}}$ Now take the ...


2

You can spot the high prime factors of $924$ - which exist by Bertrand's Postulate. Here you see $11$ and $7$ and the highest value for $r$ which avoids cancelling $7$ is $6$, which happens to be the only possibility. This would work more generally to reduce the possbilities. Note that if a high prime doesn't appear in the factorisation that puts a ...


2

This is $\sum k(k-1)\binom{n}{k}$ which is $f''(1)$ where $f(x)=\sum\binom{n}{k}x^k=(1+x)^n$



Only top voted, non community-wiki answers of a minimum length are eligible