Tag Info

Hot answers tagged

10

Put $$a_n = \frac{n!^{1/n}}{n}$$ then $$\log a_n = \frac{1}{n}\left(\log n! - n\log n\right)= \frac{1}{n}\sum_{k=1}^n\log\left(\frac{k}{n}\right)$$ where we have used $\log n! = \log 1 + \log 2 + \ldots + \log n$. The sum above is a Riemann sum for the integral $\int_0^1\log x dx$ so $$\lim_{n\to\infty} \log a_n = \int_0^1\log x dx = [x\log x - x]_0^1 = ...


8

You have all the right pieces, but it's pretty sloppy. Here's a cleaned up version. We will prove by induction on $n \in \mathbb N$ that: $$ 1! + 2! + \cdots + n! < (n + 1)! \tag{$\star$} $$ Base Case: Notice that $(\star)$ holds for $n = 1$, since: $$ 1! = 1 < 2 = (1 + 1)! $$ Inductive Step: Assume that $(\star)$ holds for $n = k \geq 1$. It ...


5

First, by dividing both sides by $(n!)^2$ and organizing the factorials into binomial coefficients we obtain the suggestive form $$\binom{2n}{n}\overset{?}{=}\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{k}\binom{n-k}{k}2^{n-2k}$$ We verify this expression by a double counting argument. Consider a $2\times n$ array consisting of equal numbers of zeros and ...


5

You have a total of $xy$ balls, namely $y$ balls of each of $x$ colors. In how many ways can you arrange these balls in a line, when two arrangements that cannot be distinguished colorwise are considered equal?


4

Proceed by induction on $m$. Clearly, if $m=1$ you have $\frac{k!}{k!} = 1$ is an integer. Now, for the inductive step consider $$\frac{((m+1)k)!}{(k!)^{m+1}} = \frac{(mk)!}{(k!)^m} \frac{(mk+1)(mk+2) \cdots (mk+k)}{k!}$$ By hypothesis $\frac{(mk)!}{(k!)^m}$ is an integer, so if you prove that $$\frac{(mk+1)(mk+2) \cdots (mk+k)}{k!} $$ is an integer you are ...


4

Another possible approach is to use the discrete Fourier transform. Let $\omega=\exp\frac{2\pi i}{3}$. Then: $$f(n)=\frac{1}{3}\left(1+\omega^n+\omega^{2n}\right)=\mathbb{1}_{n\equiv 0\!\pmod{3}}(n),$$ hence: ...


4

Hint: $\left(n+1\right)!=n!\left(n+1\right)>n^{\frac{n}{2}}\left(n+1\right)$. So it is enough to prove that: $$n^{\frac{n}{2}}\left(n+1\right)\geq\left(n+1\right)^{\frac{n+1}{2}}$$ or equivalently: $$n+1\geq\left(1+\frac{1}{n}\right)^{n}$$ This for $n>2$.


4

Hint: $n$, $(n+1)$, $(n+2)$, $(n+3)$, $(n+4)$, $(n+5)$ are all 6 consecutive numbers so one of them is a multiple of 6, and 3 of them are a multiple of 2; and 2 of them are a multiple of 3...


4

Hint: $$ \sum_{n=k}^m\binom{n}{k}=\binom{m+1}{k+1} $$ A generalization is discussed in this answer. The equation above is equation $(1)$ with $m=0$. Telescoping sum To turn the sum in the question into a "telescoping sum", we can use the recurrence for Pascal's Triangle: $$ \binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1} $$ Using this recurrence, we get $$ ...


4

Let $$p_n=\prod_{r=1}^k (n+r)=\overbrace{(n+1)(n+2)\cdots(n+k)}^{k \ \text{terms}}$$ which is the product of $k$ consecutive integers. Consider the difference of two consecutive terms, where each term is the product of $k+1$ consecutive integers, i.e. $$\begin{align} &\prod_{r=1}^{k+1}(n+r)-\prod_{r=0}^k(n+r)\\ ...


4

Stirling's Approximation $$ n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n $$ Which means that $n!$ is asymptotically equivalent to $\sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ as $n$ approaches $\infty$. If your familiar with asymptotic formulas, then you'd also know that this implies that $$ \lim_{n\to\infty} \frac{n!}{\sqrt{2\pi ...


3

Also a neat way to solve it without induction $$\sum_{r=1}^nr\cdot r!=\sum_{r=1}^{n}(r+1-1)\cdot r!=\sum_{r=1}^n (r+1)!-r!=(n+1)!-1$$ Since all terms cancel out except $(n+1)!$ and $-1$


3

Here is a simple elementary proof I found, but first of all, some lemmas: This one could easily be proven by induction: $\displaystyle \prod_{k=1}^{n}\left(1+\frac{1}{k} \right) = n+1$ You can try to prove this inequality yourself since it's not difficult: $\displaystyle \left (1+\frac{1}{k} \right )^k\leq e \leq \left (1+\frac{1}{k} \right)^{k+1}\\$ This ...


3

Divide $x$ by $2$, then divide by $3$, and so on, until you cannot divide further. If you arrive at the number $1$, you started with a factorial. Otherwise you didn't.


3

Hint #1: Look at Stirling's approximation. Hint #2: $\ln n^{\ln n} = \left(e^{\ln \ln n}\right)^{\ln n} = e^{\left(\ln n\cdot \ln\ln n\right)} = ?$ (Note that I use $\ln$ rather than $\lg$, but the bases of the logs don't make any real difference here - convince yourself of that, though!)


3

Since $4!$ is congruent to $0$ (mod $12$) then any multiple of $4!$ is congruent to $0$ (mod $12$). So we need only look at the first 3 terms, and since each of the first 3 terms is congruent to themselves (mod $12$), then the addition of all the terms in (mod $12$) is: $(1! + 2! + 3! + 0 + 0 +...+ 0)$(mod 12). So the remainder should be 9.


3

$$\frac{(mk)!}{k!^m}=\frac{\color{red}{(1.2\cdots k)}\color{green}{((k+1).(k+2)\cdots(2k))}\cdots\color{blue}{(((m-1)k+1).((m-1)k+2)\cdots(mk))}}{\color{red}{k!}.\color{green}{k!}\cdots\color{blue}{k!}}$$ Does that gave you some HINT?


2

$ 1! + 2! + \cdots + n! \le n! + n! + \cdots + n! = n\cdot n! < (n+1)\cdot n! = (n + 1)! $


2

My other answer was answering a very different question. Looking at Wikipedia's description of fractional values in a factorial number system, it says that $e$ can be represented as $10_F1111111\ldots$, i.e. as $1\times2! +0\times 1! +1\times\frac1{2!}+1\times\frac1{3!}+1\times\frac1{4!}+1\times\frac1{5!} + \cdots$. Note that Wikipedia omits any digits ...


2

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} ...


2

I actually performed the calculation(all by hand,none with calculator). $$\zeta=\frac{30.29.28.27.26.25.24.23.22.21.20.19.18.17.16.15.14.13.12.11}{5.4.3.2.1.50.49.48.47.46.45.44.43.42.41.40.39.38.37.36} $$ Cancelling(Writing explicitly took me 1 min $[9:10\to9:11]$ and cancelling took me 3 mins$[9:12\to9:15]$): $$\zeta=\frac{9.11.13.17.29}{37.41.43.47}$$ ...


2

It depends on the accuracy you are looking for the approximation. A standard tool to approximate large binomial coefficients is the Central Limit Theorem. We have that: $$\frac{1}{2^{30}}\binom{30}{10}\approx \sqrt{\frac{2}{30\pi}}\cdot e^{-\frac{2(15-10)^2}{30}},$$ $$\frac{1}{2^{20}}\binom{20}{5}\approx \sqrt{\frac{2}{20\pi}}\cdot ...


2

HINT : $$(2k+1)!!=1\cdot 3\cdot 5\cdot \cdots (2k-1)\cdot (2k+1)$$ $$(2k+1)!=1\cdot 2\cdot 3\cdot \cdots (2k)\cdot (2k+1) $$ $$2^k\cdot k!=2^k\times \{1\cdot 2\cdot 3\cdot \cdots (k-1)\cdot k\}=2\cdot 4\cdot 6\cdot\cdots (2k-2)\cdot (2k).$$


2

Hint: Note that $4!\equiv 0\pmod{12}$.


2

Derivatives and Integrals make sense only for non integer functions. If you like a function that "flows". If you want to find the derivative of the factorial function you could consider extending it to the real numbers using the Gamma function. The gamma function acts like the factorial function for all positive integers however it also has values for real ...


2

Note that $$ (2n+1)!=(2n+1)(2n+1-1)(2n+1-2)\cdots 1 $$ And $$ (2n-1)!=(2n+1-2)\cdots 1 $$ So $$ (2n+1)!=(2n+1)(2n)(2n-1)! $$


2

Here is an idea to do something less time consuming if $x$ randomly chosen, ie. not in $\mathbb{F}$ most of the time. It assumes that divisions by powers of 2 and additions are free compared to divisions by odd numbers, and tries to avoid them as much as possible. Compute how many times $x$ is divided by $2$, that is the max $p$ such as $x = 2^p*...$. That ...


2

You've already checked that when $n=-1$, then you get the equality you want, so that is definitely a solution. You can ignore the case $n=-6$ because the factorial is not defined for $n<0$. Your solution is correct. The reason why the other "solution" $n=-6$ showed up is because it is a solution to the equation $(n+4)(n+3)=6$, which allows $n$ to be any ...


2

Hint. Take the natural logarithm of $\dfrac{(n!)^{1/n}}{n}$ and obtain $$ \frac{\log 1+\log 2+\cdots+\log n}{n}-\log n=\frac{\log (1/n)+\log(2/n)+\cdots+\log(n/n)}{n} \\=\frac{1}{n}\sum_{k=1}^n\log\left(\frac{k}{n}\right) \to \int_0^1 \log x\,dx=-1. $$



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