New answers tagged

1

Well, considering that the positive integers have Lebesgue measure 0 in R, any integral over a set over which the factorial is defined without the gamma function necessarily evaluates to 0 as well.


0

In short, it's because the integral is a continuous operator, while the factorial function is not. However, if you want to look into this more, check out the Wikipedia article for the Gamma function.


1

Okay... Is there only one solution? Well, yeah... because $n!$ increases by a factor of $(n+1)!/n! = n+1$ as $n$ increases by one, while $n(n+1)(n+2)(n+3)$ only increases by $(n+1)(n+2)(n+3)(n+4)/n(n+1)(n+2)(n+3) = (n+4)/n = 1 + 4/n$. As $n!$ increases faster for $n > 2$ there is at most one solution. (Unless there is a solution for $n = 1$ or $0$ ...


0

Since you are calling for intuition, you may know that a fundamental property of the natural exponential is that it is equal to its derivative. Suppose that $$ f(x) = \sum_{n=0}^\infty a_n{x^n}\,,$$ is equal to its derivative. Then formally, $$ f'(x) = \sum_{n=1}^\infty n a_n{x^{n-1}}\,,$$ thus $$ f'(x) = \sum_{n=0}^\infty (n+1) a_{n+1}{x^{n}}\,,$$ thus, ...


3

This is quite a nice problem, though a proper solution is pretty involved for a job interview. Here's a compact way to repackage this: The largest power $k$ of a prime $p$ that divides $n!$ is the $p$-adic valuation $$v_p(n!) := \sum_{k = 1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor$$ of $n!$. Expanding this necessarily finite sum and applying a ...


10

No, not if you're going to disallow the gamma function and require that $x$ be an integer. The reason is that $\int x! \, dx$ represents a function $f(x)$ such that $f'(x) = x!$. But $x!$ is defined only on the integers. So if such an $f(x)$ were to exist then $f'(x)$ would exist only on a countably infinite set of isolated points. In the context of ...


15

Since $\gcd(n,n-1)=1$, no prime factor of $n-1$ divides $n$. And since $n>2$, there must exist a prime dividing $n-1$.


0

I see the four-horse exacta box as being an application of hypergeometric math, i.e.,the same math used to calculate lotto odds, with N = field; K = horses "drawn" (4); B = two "winning" horses, 1 & 2. If my view is incorrect, then how does the four-horse box differ from the lotto model? Even if the hypergeometric model is correct, how can odds be ...


2

Recall $$f_n (z) = \sum_{k=0}^n \binom{n}{k} z^k = (1+z)^n,$$ by the binomial theorem. Now observe for $0 \le m \le k \le n$, $$\begin{align*} \binom{k}{m}\binom{n}{k} &= \frac{k!}{m! \, (k-m)!} \cdot \frac{n!}{k! \, (n-k)!} \\ &= \frac{n!}{m! \, (k-m)! \, (n-k)!} \\ &= \frac{n!}{m! \, (n-m)!} \cdot \frac{(n-m)!}{(k-m)! \, (n-k)!} \\ &= ...


6

Suppose that you want to choose a committee from $n$ people so that this committee has a president and a vice-president. The smallest committee here would have just a president and a vice-president (two members). One way to find the number of ways to do this is to sort by committee size and sum them up (as they are ...


3

$$\sum_{k=2}^{n}k\left(k-1\right)\binom{n}{k}=\sum_{k=2}^{n}\frac{n!}{\left(k-2\right)!\left(n-k\right)!}=n\left(n-1\right)\sum_{k=2}^{n}\binom{n-2}{k-2}=\cdots$$


4

I'm not sure how to proceed with your induction proof. A more direct approach is to write: $$\begin{align}k(k-1)\binom{n}{k}&=k(k-1)\frac{n!}{k!(n-k)!}\\ &=n(n-1)\frac{(n-2)!}{(k-2)!(n-k)!}\\ &=n(n-1)\binom{n-2}{k-2} \end{align}$$


5

Consider the classical binomial identity under the form $$\sum _{k=0}^{n} {n \choose k}x^k=(1+x)^{n}$$ derivate twice, then replace $x$ by 1.


2

Much more is true. If $(x_i)$ is a set of $n$ reals with $x_i \ge 1$, then $\left(\frac1{n}\sum x_i\right)! \le (\prod x_i!)^{1/n} $, or $\left(\frac1{n}\sum x_i\right)!^n \le \prod x_i! $. This is because the factorial function is log-convex. Here is the proof. Jensen's inequality states that if $f$ is a convex function ($f''(x) \ge 0$) then ...


0

$x = k + \alpha,y = k + \beta, z = k+\gamma$ $\alpha + \beta + \gamma = 0$ Without loss of generality we can insist that $\alpha \leq \beta \leq \gamma $ Suppose, $\beta < 0$. $\alpha +\beta = - \gamma$ $x!y!z! = (k!)^3 \dfrac{(k+1)(k+2)...(k+\alpha)(k+\alpha+1)...(k+\gamma)}{(k-1)(k-2)...(k-\alpha)(k-1)...(k-\beta)}\geq (k!)^3$ In that fraction ...


4

Lemma. If $a,b$ are integers with $0\le a<b$ then $a!b!\le(a+1)!(b-1)!$ with equality iff $b=a+1$. Proof. Indeed, $a!b! = a!(b-1)!\cdot b\stackrel{(*)}\ge a!(b-1)!\cdot(a+1)=(a+1)!(b-1)!$ and equality at $(*)$ holds iff $b=a+1$. $\square$ Fix $k\in\Bbb N$ and consider $$ A:=\{\,x!y!z!\mid x,y,z\in \Bbb N_0, x+y+z=3k\,\}.$$ As a finite set, $A$ ...


0

You're getting the answer for $\Gamma(11/2)$, where $$\Gamma(n)=(n-1)!$$ The gamma function $\Gamma(x)$ is defined for all $x$ except $0, -1, -2, -3, ...$. The factorial function, however, is defined only for positive integers.


0

Using the Gamma function we have $$(9/2)!=\Gamma(11/2)=\frac{945}{32}\sqrt{\pi}=52.3427777 $$


1

factorial is defined only for positive integers. But it is generalized to real numbers using the gamma function. For each positive integer n, you have $\Gamma(n+1)=n!$. You have that $\Gamma(5.5)=52.342777..$


1

$$ \lim_{n\to \infty} \frac{(n+1)!}{n!}=\lim_{n\to \infty} (n+1) = +\infty$$ which implies $(n+1)!$ is not $O(n!)$.


0

We can read octo factorial numbers in the synopsis of the OEIS sequence A049210 which is addressed by OP. Octo factorial numbers are identified as A051189 and defined as \begin{align*} \left(n!\cdot 8^n\right)_{n\geq 0}=(1, 8, 128, 3072, 98304,\ldots) \end{align*} Here we have a variant in some weird notation which can be written as ...


0

Speculation: What I see when I visit OEIS is A049210 a(n) = -product_{k=0..n} (8*k-1); octo-factorial numbers. In the unix bash shell the symbol "!" means "repeat the previous command". Perhaps in this context "(!^8)" means something like "replace $n$ with $n-8$ in the formula for $a(n)$, so defining a recursion. You could check to see if that ...


1

From the context, it seems that we have a recursion $n(!^k)=(n-k)(!^k)\cdot n$ and $m(!^k)=m$ for $1\le m<k$. This makes $n(!^1)=n!$ and $n(!^2)=n!!$.


1

See the terms having factor $11$ are $11,22,33,..121,...220,..297$ so excluding $121,242$ we have $25$ numbers which give only one $11$ and $121,242$ gives two $11$ so total exponent is $11^{25}.11^4=11^{29}$


1

$$\require{cancel} \frac{n!}{3!\cdot(n-3)!} = 2\cdot\frac{n!}{2!\cdot(n-2)!}$$ Dividing by $n!$ and collecting constants: $$\frac{1}{(n-3)!} = \frac{6}{(n-2)!}$$ $$6=\frac{(n-2)!}{(n-3)!}=\frac{(n-2)\cancel{(n-3)(n-4)(n-5)...}}{\cancel{(n-3)(n-4)(n-5)...}}$$ $$6=n-2$$ $$\therefore n=8$$


1

$$3!(n - 3)! = (n - 2)! \Leftrightarrow 6=n-2 \Leftrightarrow n=8$$


1

The last inequality can be written as $$(n+1)\cdot\left((n+1)!^{\frac{1}{n+1}}-1\right)<n\cdot n!^\frac{1}{n}$$ or: $$(n+1)\cdot (n+1)!^{\frac{1}{n+1}} -n\cdot n!^\frac{1}{n}< n+1$$ that is straightforward to prove through Stirling's approximation: it gives that the LHS behaves like $\frac{2}{e}\cdot(n+1)$ and $\frac{2}{e}<1$.


4

Step II. This Assume $8^n \vert (4n)!$ is true for all $n$ is absoultely WRONG. This is your theorem to prove — once you assume it is true, it became an axiom instead of a theorem. Say instead: Assume $8^n \vert (4n)!$ is true for some $n$ then show it implies that $8^{n+1} \vert (4(n+1))!$, consequently, based on the principle of induction, ...


2

From the expression: $(4n+4)(4n+3)(4n+2)(4n+1)[(4n)!]$ Note that by the I.H., $8^n|(4n)!$, thus we need only show that: $8|(4n+4)(4n+3)(4n+2)(4n+1)$ Which we can do by factoring out common factors from the linear factors. Observe that $(4n+4)=4(n+1)$ and $(4n+2)=2(2n+1)$, hence we can rewrite $(4n+4)(4n+3)(4n+2)(4n+1)$ as $4(n+1)(4n+3)\cdot ...


5

The most important part is the inductive step, where you said "Assume $8^n|(4n)!$ for all $n$" (for all $n\in\mathbb{N}$). The problem here is that you just assumed what you were trying to prove. Compare this statement to the original problem and you will find they are identical. What we want to do is show that if $8^n|(4n)!$ for some $n\in\mathbb{N}$, then ...


2

First, show that this is true for $n=1$: $(4\cdot1)!=8^1\cdot3$ Second, assume that this is true for $n$: $(4n)!=8^nk$ Third, prove that this is true for $n+1$: $(4(n+1))!=$ $(4n+4)!=$ $\color{red}{(4n)!}(4n+1)(4n+2)(4n+3)(4n+4)=$ $\color{red}{8^nk}(4n+1)(4n+2)(4n+3)(4n+4)=$ $8^nk(256n^4+640n^3+560n^2+200n+24)=$ ...


2

In step II you say: $8^n | F(n) => F(n)=8^v $ That's false. You should write. $8^n | F(n) => F(n)=k*8^n $ So at step III you will have $F(n+1)=t*F(n) => F(n+1) = t*k*8^n$ If you prove that $8|t$. (ie: $t = 8*t'$) You will have: $F(n+1) = k*8*t'*8^n = k*t'*8^{(n+1)}$ hence $8^{(n+1)} | F(n+1)$ Q.E.D.


2

We have $$23!-21!=(23)(22)(21!)-21!=(21!)((23)(22)-1)=(21!)(505).$$ Note that $101$ divides $505$.


1

Use the fact for any integer $n$, one of the numbers inside $n,n+1,n+2,n+3$ divisible by $4$ and one of them is divisible by $2$ but not $4$. This easy fact says us any $4$ consecutive integers divisible by $8$. We will use this fact in induction step.


3

Good so far, to finish up just note that $$(4(n + 1))! = (4n + 4)! = (4n + 4)(4n + 3)(4n + 2)(4n + 1)(4n)!.$$ Since $4$ divides $(4n + 4)$ and $2$ divides $(4n + 2$), we have that $8$ divides $(4n + 4)(4n + 3)(4n + 2)(4n + 1)$. By the induction hypothesis, $8^n$ divides $(4n)!$. Therefore $8^{n+1}$ divides $(4(n + 1))!$, completing the induction step. You ...


5

Well, you know that $(4n)! = 8^nk$ for some integer $k$. $$\Rightarrow (4n + 4)! = (4n+4)(4n+3)(4n+2)(4n+1)(4n)!$$ $$ = 8^nk(4n+4)(4n+3)(4n+2)(4n+1)$$ Factor out of the even terms: $$ = 8^n 8 k (n+1)(4n+3)(2n+1)(4n+1)$$ $$= 8^{n+1} k'$$ For some integer $k'$. This means that $(4n+1)!$ is divisible by $8^{n+1}$.


2

HINT: What is $\dfrac{23!}{21!}$? And what is that modulo $101$?


2

You are correct, $n^n$ does grow faster than $n!$ -- hence $n!$ is $O(n^n)$. However, induction doesn't make sense here. You are confused by the notation -- "big O" statements don't involve numbers n, it is a statement on functions, $f(n) = n!$ and $g(n) = n^n$. Try writing out $n^n$ and $n!$ in terms of products. $n! = n * (n-1) * ... * 1$. Compare this ...


0

Here is a combinatorial argument that $2^n\leq (n+1)!$ for all nonnegative integers $n$. Consider a sequence $\left(a_0,a_1,a_2,\ldots,a_n\right)$ where $\left\{a_0,a_1,a_2,\ldots,a_n\right\}=\{0,1,2,\ldots,n\}$. There are $(n+1)!$ such sequences. If $\mathbf{a}:=\left(a_0,a_1,a_2,\ldots,a_n\right)$ is such a sequence, we say that $\mathbf{a}$ is ...


1

Your reasoning is dodgy. You would need to demonstrate that "the property gets more true as $k$ increases, so the worst case is when $k=0$, which we now prove". But if you're starting out, that's not a good line of reasoning to follow, and it can get you into bad habits. If $2^k < (k+2)!$, how can we transform the inequality to get $2^{k+1}$ on the ...


1

You must use $2^n < (n+2)!\Rightarrow 2^{n+1} = 2\cdot 2^n < 2\cdot (n+2)!< (n+3)\cdot (n+2)!=(n+3)!$


0

Hint: The challenge in induction problems with an inequality is the inequality. You won't get the same formula on both sides like you would in an induction with an equality (you do some manipulation and the formulas pop out). In this problem, you are correct that the $n=1$ case is fairly easy, so you assume that for $n=k$, the statement is true; i.e., ...


0

If you want to do it without induction, by the way, it's immediate from the AM/GM inequality.


2

From : $$ v_p(m!)=\sum_{i=1}^mv_p(i). $$ We can obtain, for a big enough $n$ : $$v_{p}(m!) = \left| \left\{k \mid pk \leqslant m \right\} \right| + \left| \left\{k \mid p^{2}k \leqslant m \right\} \right| + ... + \left| \left\{k \mid p^nk \leqslant m \right\} \right|$$ Indeed, if $i$ is such that $v_p(i) = m$, i will be in the $m$ first sets. Thus we ...


2

My comments from the other question apply here as well. But we actually can define $Z(a,n)$ even with such a mild class of functions as one including the ceiling function, addition, subtraction, and division. $$Z(a,n) = \left\lceil \frac {n-1}a - \left\lceil \frac{n-1}{a} \right\rceil \right\rceil.$$ Actually, the example you gave in the comments extends ...


5

The remainder of binomial coefficients with respect to primes is given by Lucas' theorem: For non-negative integers $m$ and $n$ and a prime $p$, $$\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\bmod p\;,$$ where $m_i$ and $n_i$ are the $i$-th digits of $m$ and $n$, respectively. To find the last digit of a binomial coefficient, we need its remainders ...


1

Let $n:=p-\alpha$ and $r:=q-\alpha$. Then, from the identity $\displaystyle\binom{q}{\alpha}\,\binom{p}{q}=\binom{p}{\alpha}\,\binom{p-\alpha}{q-\alpha}$, the equality $\displaystyle\sum_{q=\alpha}^p\,\binom{q}{\alpha}\,\binom{p}{q}\,\frac{(-1)^q(-q)^p}{q^\alpha}=\frac{p!}{\alpha!}$ holds if and only if ...


2

For my own convenience I’m going to replace your $\alpha,p$, and $q$ with $m,n$, and $k$, respectively. Fix $n$, and let $$f(m)=\sum_k\binom{k}m\binom{n}k(-1)^{n+k}k^{n-m}=\sum_k(-1)^{n-k}\binom{n}kk^{n-m}\frac{k^{\underline{m}}}{m!}\;,$$ where $x^{\underline{m}}=x(x-1)\ldots(x-m+1)$ is a falling factorial. Now $$\begin{align*} ...


1

check out the Gamma function, an extension of the factorial function to the real (and complex) numbers


3

Suppose we seek to verify that $$(-1)^p \sum_{q= r}^p {p\choose q} {q\choose r} (-1)^q q^{p- r} = \frac{p!}{ r!}.$$ We use the integral representation $${q\choose r} = {q\choose q- r} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{q}}{z^{q- r+1}} \; dz$$ which is zero when $q\lt r$ (pole vanishes) so we may extend $q$ back to zero. We also use ...



Top 50 recent answers are included