Hot answers tagged

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


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


7

We count the number of permutations of $1,2,3,\ldots, n+1$ in two ways. First, it is equal to $(n+1)!$. To get the other count, split into cases based on the size of the initial segment agreeing with the identity permutation $[1,2,3,\ldots, n,n+1]$. For example, $[1,2,4,3]$ agrees with $[1,2,3,4]$ for the first $2$ places, whereas $[2,4,1,3]$ agrees with ...


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


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.


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


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


5

$(n+1)!=2\cdot 3\cdot \dots\cdot(n+1)$ here a product of $n$ numbers all are at least 2 so the result follows...


5

Hint: $(6n + 5)! = (6n + 5)(6n + 4)(6n + 3)(6n + 2)(6n + 1)(6n)(6n - 1)!$


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


4

Nothing much changes, even if you ask $$ x! = 2^y + 8. $$ As soon as $x \geq 6,$ we have $x!$ divisible by $16.$ As soon as $y \geq 4,$ we know $2^y + 8$ is not divisible by $16.$ Since $6! = 720,$ we would need $y \geq 9,$ guaranteed failure. So $x \leq 5.$ As pointed out by @marty the same reasoning applies to $$ x! = 2^y - 8, $$ with solution $x=5, ...


4

HINT: $$\frac{(n+1)!}{2^n}=\frac{2}{2}\frac{3}{2}\frac{4}{2}\cdots \frac{n-1}{2}\frac{n}{2}\frac{n+1}{2}$$


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


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


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


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


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


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


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


2

Use Stirling's approximation $$ n!\sim \sqrt{2\pi n} (n/e)^n $$ for large $n$ to write $$ \frac{(3n)!(1/27)^n}{(n!)^3}\sim\frac{\sqrt{2\pi 3 n} (3n/e)^{3n} (1/27)^n }{(\sqrt{2\pi n} (n/e)^n)^3 }=\frac{\sqrt{3}}{2n\pi}\to 0 $$ for large $n$.


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


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


2

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.


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)!} \\ &= ...


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


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


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


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

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

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



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