# Tag Info

2

$$f(n) = \frac{1}{(2n+1)!(2n+1)}$$ we know that $$f(n+1) < f(n)$$ i.e. strictly decreasing function with $n$. thus trying a few values of $n$ we find \begin{align} \text{n=4: } \frac{1}{9!9} &=& \frac{1}{3265920}\approx 3\times10^{-7}\\ \text{n=5: } \frac{1}{11!11} &=& \frac{1}{439084800}\approx 2\times10^{-9}\\ \text{n=6: } ...

-1

$$(v+1)! = 1 + \sum_{k=1}^v (v-k-1)! (v-k)^2$$

1

It's fine but instead of subtracting the terms you could try dividing them and find if $a_{n+1}/a_n\ge 1$, that would be simpler.

1

Since $$\log(n!) = \sum_{k=1}^n \log k$$ and the logarithm is an increasing function, $$\log(n!)\leq \int_{1}^{n+1}\log x\,dx = -n+(n+1)\log(n+1)$$ and exponentiating both sides: $$n! \leq e^{-n} (n+1)^{n+1}$$ so: $$n! \leq en\cdot e^{-n}n^{n}$$ follows from $n!=n\cdot(n-1)!$.

1

What power of $3$ divides $100!$? $\left\lfloor\frac{100}{3}\right\rfloor$ for all the multiples of $3$ in $\{1,2,3\ldots,100\}$. Additionally, $\left\lfloor\frac{100}{9}\right\rfloor$ for all the multiples of $9$. Additionally, $\left\lfloor\frac{100}{27}\right\rfloor$ for all the multiples of $27$. Additionally, ...

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 ...

1

Inductive reasoning: $$n!\leq en(\frac{n}{e})^n=\frac{n^{n+1}}{e^{n-1}}$$ Then must prove $$(n+1)!=(n+1)n!\leq \frac{(n+1)n^{n+1}}{e^{n-1}} \stackrel{?}{\leq} \frac{(n+1)^{n+2}}{e^n }$$ if and only if: $$n^{n+1}e<(n+1)^{n+1}$$ $$e<(1+\frac{1}{n})^{n+1}$$ if and only if: $$ln(e)<(n+1) ln(1+\frac{1}{n})$$ $$1<(n+1) ln(1+\frac{1}{n})$$ The ...

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.

1

Here is another solution via group theory. Consider the group $S_n$, it has $n!$ elements. Now consider the subgroup of $S_n$ consisting of the permutations such that elements in $\{1,2,3\dots k\}$ always go to elements of $\{1,2,3\dots k\}$, it has order $k!(n-k)!$ so by lagrange's theorem $k!(n-k)!$ divides $n!$

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 ...

0

For example, to simplify $6!$, substitute $6$ for $n$ in the following equation:$$n!=n\cdot(n-1)\cdot(n-2)\cdot(n-3)\cdot...$$$$6!=6\cdot(6-1)\cdot(6-2)\cdot(6-3)\cdot(6-4)\cdot(6-5)$$and now simplify:$$6!=6\cdot5\cdot4\cdot3\cdot2\cdot1$$but you don't have to including the $1$ because it's the same thing as not using it:$$6!=6\cdot5\cdot4\cdot3\cdot2$$Now ...

0

I am going to provide a different way of going about it--this is essentially Brian M. Scott's proof in reverse. As people have pointed out, if you can show that $n! > 2^n$, then you will have shown that $n! \geq 2^n$ (in this sense, you can think of $>$ as stronger than $\geq$ because $>$ implies $\geq$). When considering $n! \geq 2^n$ and how you ...

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$.

0

Note: One way to model this problem with mathematical / CS notation is: Defining an alphabet $\Sigma$, which means the set of allowed symbols: $$\Sigma = \{ i, j, k \} \quad (i,j,k \in \{ 0, \ldots , 9 \} \wedge i \ne j \wedge i\ne k \wedge j\ne k)$$ where I might have omitted the inequalities, because set members have to be unique. The maximum ...

1

I may misunderstand this question, but if I'm supposed to add up all the numbers from 1 to 100, I would visualize 50 pairs of numbers like this: 1 + 100 = 101, 2 + 99 = 101, and then jump to the conclusion that 50 times 101 is 5050. Someone else may have suggested this.... I didn't read all the answers.

1

1) Yes, this is correct. 2) The assumption you can't seem to prove, namely that $2k<x$, is true, but it is not a trivial result (which is why it isn't easy to prove it). It's known as Bertrand's postulate. The full statement is: For any positive integer $n$, there exists a prime number lying between $n$ and $2n$. 3) There might be a way to ...

0

Yes, the proof is correct. In other words, consider the largest prime $p$ not exceeding $x$. And if $2p<x$ then by Bertrand's postulate there exist a prime $p_1>p$, a contradiction. so $x!$ cannot be a prefect square or perfect power also.

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.

1

Here is an idea I had (by no means a complete answer but a start nonetheless), where I assume you have verified the base case and all that jazz: \begin{align} [(k+1)!]^2 &= (k+1)^2(k!)^2\\[1em] &\leq (k+1)^2\left[\frac{(k+1)(k+2)}{6}\right]^k\\[1em] ...

0

let $V_{p}(a)$ is the exponent of the prime number $p$ in the prime factorization of $a$,then we know $$v_{p}(n!)=[\dfrac{n}{p}]+[\dfrac{n}{p^2}]+[\dfrac{n}{p^3}]+\cdots=\sum_{i=1}^{\infty}[\dfrac{n}{p^k}]$$ so Now we only prove $$2\sum_{k=1}^{\infty}[\dfrac{2n}{p^k}]+\sum_{k=1}^{\infty}[\dfrac{i}{p^k}]+\sum_{k=1}^{\infty}[\dfrac{j}{p^k}]\ge ... 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 ... 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 ... 0 n \cdot n! = (n+1-1)n!=(n+1)n!-n!=(n+1)!-n! Now, sum of all this taking n=1,2,3,... 1 \cdot 1!+2 \cdot 2! + 3 \cdot 3! + ... + n \cdot n!$$=(2!-1!)+(3!-2!)+(4!-3!)+...+((n+1)!-n!)=(n+1)!-1!$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 ... 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 ... 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. 0 Why use induction here? Just consider$\frac{1 \cdot 2 \ldots n}{2 \cdot 2 \ldots 2}$There are$n-1$terms in the numerator after the first one and$n-1$in the denominator. Clearly the numerator is monotone increasing and$k>2 \ \forall \ k \geq 2$, so the fraction is greater than 1. 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}.$3 Use your induction hypothesis and$n+1>2$. 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$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}$$ 1 I'll assume the generalized binomial coefficient is defined via the gamma function, with$\binom{x}{y}=\frac{\Gamma(x+1)}{\Gamma(y+1)\Gamma(x-y+1)}This will match the normal definition for integers, and will follow most of the familiar properties. When dealing with the gamma function, the most important properties to remember are that ... 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}\\\\ ... 2 \binom{-1/2}{ n} = (-1/2)(-3/2)(-5/2)\ldots(-(2n-1)/2) /n! = (-1)^n 1\cdot 3\cdot 5\cdot\ldots\cdot(2n-1)/ (2^n n!) = (-1)^n (2n)!/ (2^n \cdot n! \cdot 2 \cdot 4 \cdot 6\cdot \ldots \cdot (2n)) = (-1)^n (2n)!/ (2^n n!)^2 = (-1/4)^n \binom{2n}{n}. $$Hence:$$ (1-4X)^{-1/2} $$generates (link)$$ \binom{2n}{n}.$$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 ... 0 For the special case a=\frac{1}{2} we can get a closed form. I didn't give an answer to the general solution however. Write it down as a product. This gives$$\prod_{k=0}^n (a-k)$$We'll put a=\frac{1}{2} and see what this gives. By substitution we have$$\prod_{k=0}^n (\frac{1}{2}-k)=\prod_{k=0}^n\frac{1-2k}{2}$$Now write out the nth partial ... 0 Suppose we are trying to evaluate$$\sum_{q=0}^n {n\choose q} (-1)^q (k-q)^n.$$Observe that$$(k-q)^n = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((k-q)z) \; dz.$$This gives for the sum the integral$$\frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{q=0}^n {n\choose q} (-1)^q \exp((k-q)z) \; dz \\ = \frac{n!}{2\pi ... 3 More generally ifp$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 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 ... 0 I think that a way to add all the digits in hundred is add the even numbers then all the odd numbers. I tried this and it really worked out. Or another way is to keep on adding the number you started out with (small) and then taking a chart with all the numbers from 1 through 100 and ticking it of when you have reached the number or when you have came to ... 0 For a number n, define \Lambda(n)=\log p if n=p^k and zero elsewhen. Note that \log n=\sum\limits_{d\mid n}\Lambda(d). If N=n!, then$$\log N=\sum_{k=1}^n\log k=\sum_{k=1}^n\sum_{d\mid k}\Lambda (d)=\sum_{d=1}^n \Lambda(d)\left\lfloor \frac nd\right\rfloor$$Since \Lambda(d) is nonzero precisely when d is a power of a prime and in such case ... 1 Hint: By the rule of integer division,$$M.q=N!-N!\bmod M,$$where we are interested in the parity of the quotient q. We can rewrite$$M.(2.(q\text{ div }2)+q\bmod 2)=N!-N!\bmod M.$$Then, taking the \bmod 2,$$(M\bmod2).(q\bmod2)=(N!-N!\bmod M)\bmod2.$$Now, assuming M odd, the parity of q can be obtained as the parity of N!-N!\bmod M, ... 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 ... 0 Here is one way you can attack this problem. I will not write the full analysis, but enough to give an idea. Start with assuming we have$$ \frac1{\sqrt{1-z}} = \sum_{k=0}^\infty a_k z^k $$Then, computing the square, we find that$$ \frac1{\sqrt{1-z}} \cdot \frac1{\sqrt{1-z}} = \frac1{1-z}= \sum_{k=0}^\infty a_k z^k \cdot \sum_{l=0}^\infty a_l z^l $$... 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 You're right it can be simplified $$9\frac{(2k)!}{(2k+2)(2k+1)(2k)!} = \frac{9}{(2k+2)(2k+1)}$$ 0 Similar to @Mitch's answer, but with a slight twist at the end. For anyn$, we define$n!$to be the the number of invertible functions from a set of size$n$to itself. The question is thus restated as "Prove that there is exactly one invertible function from the empty set to itself." Now, it should be clear that there can't be more than one function ... 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 = ...

1

Using the root test, $\displaystyle\lim_{n\to\infty}\frac{\left((n+1)!\right)^{1/n}\left(n+1\right)^{1-1/n}}{n^2}=\lim_{n\to\infty}\frac{\left((n+1)!\right)^{1/n}}{n}\cdot\frac{n+1}{n}\cdot\frac{1}{(n+1)^{1/n}}=\lim_{n\to\infty}\frac{\left((n+1)!\right)^{1/n}}{n}$ $\hspace{2.2 in}$since $\displaystyle\frac{n+1}{n}\to1$ and $\displaystyle (n+1)^{1/n}\to 1$. ...

Top 50 recent answers are included