Tag Info

28

HINT: $(300^{300})^{1/2}=300^{150}$, so you’re comparing $$\underbrace{300\cdot300\cdot\ldots\cdot300}_{150\text{ factors}}$$ with $$300\cdot299\cdot\ldots\cdot1=\underbrace{(300\cdot1)\cdot(299\cdot2)\cdot\ldots\cdot(151\cdot150)}_{150\text{ factors}}\;.\tag{1}$$ Show that each of the parenthesized factors in $(1)$ is at least $300$.

6

Let $A:=\{ x_1,..,x_n \}$ and $B=\{y_1,..,y_m \}$. Lets count the number of onto functions $f:A \to B$. There are $m^n$ functions from $A$ to $B$. Lets count now the ones which are not onto: Define $$P_i= \{ f : A \to B |y_i \notin f(A) \}$$ Then we need to figure out the cardinality of $\cup_i P_i$. By the inclusion exclusion principle $$|P_1 \cup ... 6 What's the problem with the ratio test?:$$\frac{a_{n+1}}{a_n}=\frac{(2n+2)!\color{red}{3^{n+1}}}{(n+1)!(\color{green}{2}(n+1))^{n+1}}\frac{n!(\color{green}{2}n)^n}{(2n)!\color{red}{3^n}}=\frac{(2n+1)\cdot3}{n+1}\left(\frac{n}{n+1}\right)^n\xrightarrow[n\to\infty]{}\frac6e>1$$and thus... 5$$x=\frac e5\implies\;\text{we have the series}\;\;\sum_{n=1}^\infty\frac{n!5^ne^n}{n^n5^n}=\sum_{n=1}\frac{n!e^n}{n^n}$$and now you can use Stirling's Approximation$$n!\sim\frac{n^n}{e^n}\sqrt{2\pi n}$$so our series behaves asimptotically (for large values of \;n\;) as the series$$\frac{n^n}{e^n}\sqrt{2\pi n}\frac{e^n}{n^n}=\sqrt{2\pi n}$$and ... 5 In this answer are three different proofs of this cancellation lemma:$$ \sum_{j=k}^n(-1)^{n-j}\binom{n}{j}\binom{j}{k} =\left\{\begin{array}{} 1&\text{if }n=k\\ 0&\text{otherwise} \end{array}\right.\tag{1} $$Inductively, we can see that any polynomial in j of degree m can be written uniquely as$$ \sum_{k=0}^mc_k\binom{j}{k}\tag{2} $$where the ... 4 Note that \log_a b = \frac{\log b}{\log a}, for any choice of base of the logarithm. (Mathematicians tend to mean the natural logarithm when they write \log.) In particular, \frac1{\log_a b} = \frac{\log a}{\log b} = \log_b a. Therefore your sum is:$$ \sum_{i=2}^{99} \log_{99!} i = \log_{99!} \left( \prod_{i=2}^{99} i \right) = \log_{99!} 99! = 1 ...

4

The problem isn't that $0!=1$, the problem is that the first term in the sequence doesn't match the pattern of the other terms. The sequence whose $n^{\text{th}}$ term is $\dfrac{(n-1)!}{n^2}$ looks like $$1,\ \dfrac{1}{4},\ \dfrac{2}{9},\ \dfrac{6}{16},\ \dots$$ whereas your sequence starts with $0$, not $1$.

4

For $n=15,\left[\frac{15}{3} \right]+\left[\frac{15}{3^2} \right]+\left[\frac{15}{3^3} \right]+\;...=6$ for $n=18$ (the next multiple of $3$) $\left[\frac{18}{3} \right]+\left[\frac{18}{3^2} \right]+\left[\frac{18}{3^3} \right]+\;...=8$ If $n\geq 18$ then $\left[\frac{n}{3} \right]+\left[\frac{n}{3^2} \right]+\left[\frac{n}{3^3} \right]+\;...\geq 8$ So ...

3

"Just compute them and compare" is the only fully failsafe method. In most cases, however, estimating the logarithms of both of $x^y$ and $y!$ using Stirling's formula will yield a conclusive result without needing to compute the two values in high detail.

3

Hint: In general, for positive integer $x,y$ we have: $y!=y(y-1)(y-2) \cdot\cdot\cdot2\cdot1$ $x^y=xxx\cdot\cdot\cdot xx$ If $x\geq y$; then $x^y\ge y!$ If $x<y$, ?! (Now this is the question!) Extra: If $\left\lceil{\frac{y}{2}}\right\rceil+1< x<y$; then $x^y\ge y!.$ (easy proof) Now, we have only the case $... 3 Suppose first that$n$is even, say$n=2m$. Then $$n!=\underbrace{(2m)(2m-1)\ldots(m+1)}_{m\text{ factors}}m!\ge(2m)(2m-1)\ldots(m+1)>m^m=\left(\frac{n}2\right)^{n/2}\;.$$ Now suppose that$n=2m+1$. Then $$n!=\underbrace{(2m+1)(2m)\ldots(m+1)}_{m+1\text{ factors}}m!\ge(m+1)^{m+1}>\left(\frac{n}2\right)^{n/2}\;.$$ 3$\dfrac{8!}{5!}\cdot ...

3

It seems that your confusion here is with the presentation of the formula; so, let me give you a slightly different description. Perhaps that description will make the notation you used make more sense. For $n\in\mathbb{N}$, we define $n!$ to be the product of all natural numbers between $1$ and $n$, inclusive: that is, $$... 3 This identity also has an algebraic proof. Suppose the sum we are trying to evaluate is given by$$\sum_{k=0}^n {n\choose k} (-1)^k (n-k)^{n}.$$Observe that when we multiply two exponential generating functions of the sequences \{a_n\} and \{b_n\} we get that$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge ...

3

There's more to it, we have $$\frac{1}{\cos z} = \sum_{n=0}^\infty (-1)^n \frac{E_{2n}}{(2n)!}z^{2n}.\tag{1}$$ Since $\dfrac{1}{\cos z}$ has poles in $(k+\frac12)\pi$ for $k\in\mathbb{Z}$ and is holomorphic everywhere else, the series $(1)$ has a radius of convergence of $\dfrac{\pi}{2}$. The Cauchy-Hadamard formula now says $$\limsup_{n\to\infty} ... 3 This has a nice proof if you interpret it in terms of probabilities. When 0<x<1, B^n_i(x) is the probability of i successes from n independent events if each event has a probability x of success. Now, suppose that in order to succeed, you need to pass two (independent) stages: step 1 has a probability u of success, and step 2 a ... 3 We usually solve this equation numerically:$$a_n=\frac{365!}{365^n(365-n)!}$$Hence a_1=1 and$$a_{n+1}=a_n.\frac{365-n}{365}$$If you want to solve a_n=p, just do a little program that computes a_n from a_1 by multiplying at each step by \frac{365-n}{365} until you find p. Here$$a_{23}=0.4927027656$$2 Simplifying your first attempt yields$$(1-c)^{-i} c^i \sum_{j=0}^n {n\choose j} {j\choose i} (1-c)^j u^j (1-u)^{n-j} .$$To evaluate the sum, observe that when we multiply two exponential generating functions of the sequences \{a_n\} and \{b_n\} we get that$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} ...

2

You have $$E_p(n!) = \sum_{k=1}^\infty \left\lfloor \frac{n}{p^k}\right\rfloor < \sum_{k=1}^\infty \frac{n}{p^k} = \frac{n}{p} \sum_{r=0}^\infty \frac{1}{p^r} = \frac{n}{p}\frac{1}{1-\frac1p} = \frac{n}{p-1},$$ and the difference is small(ish). The first sum is actually finite, all terms for $k > \frac{\log n}{\log p}$ are $0$, writing it as an ...

2

Using the definition of the Exponential Series, $$e^x=\sum_{0\le r<\infty}\frac{x^r}{r!} \implies e^x-1=x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots$$ Taking $n$th power, $$(e^x-1)^n=\left(x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots\right)^n$$ $$\text{Now, }(e^x-1)^n=e^{nx}-\binom n1e^{(n-1)x}+\binom n2e^{(n-2)x}-\cdots$$ $$=\sum_{0\le ... 2 Essentially the same answer as others have given but a slightly different way to look at it. n! is only defined for non negative integers and n! = 1 if n=0 or n = 1, n! = n \cdot (n-1)! otherwise. So for example 5!$$ \begin{align} 5! & = 5 \times 4! \\ & = 5 \times 4 \times 3! \\ & = 5 \times 4 \times 3 \times 2! \\ ... 2 I think the OP's problem here might be with the way the "\dots" notation is used in mathematics, to indicate a sequence (in this case the sequence of factors to be multiplied) by listing the first few terms and (if the sequence is finite) the last few terms, leaving it to the reader to mentally fill in the rest (on the assumption that the desired pattern ... 2 my steps:  \dfrac{8!}{5!}\cdot\dfrac{7!}{7!\cdot10!}  7! and 7! cancel out: \dfrac{8!}{5!} \cdot \dfrac{1}{10!} next:  \dfrac{8!}{5!} \cdot \dfrac{1}{10 \cdot 9 \cdot 8!}  Here, 8! cross-cancel : \dfrac{1}{5!} \cdot \dfrac{1}{10 \cdot 9}  next:  \dfrac{1}{10 \cdot 9 \cdot 5!} which is \dfrac{1}{ 10 \cdot 9 \cdot 5 \cdot4 \cdot3 \cdot2\cdot1} ... 1 It’s usually a good idea to try to turn the more complicated expression into the simpler one. Here the more complicated one is\frac{(2n+2)!}{2(n+1)!(n+1)!}\;,$$and the simpler one is$$\frac{(2n+1)!}{n!(n+1)!}\;.$$Start with the numerator (2n+2)!; can it easily be represented in terms of (2n+1)!? Yes: (2n+2)!=(2n+2)(2n+1)!. What about the ... 1 n! can be expressed as a polynomial of n:$$n! = \prod_{i=0}^n (n-i) = n^{n+1} + \cdots$$This shows that n! is a n+1-degree polynomial of n. Then, the greatest power of n that you can find in this polynomial is n^{n+1}. The greatest power that you can obtain from n!n! is n^{n+1}n^{n+1} = n^{2n+2} with coefficient 1. Also, the greatest ... 1 Going down to  3, 2, 1  is saying that it will keep multiplying until it reaches 1, which is basically saying it will keep multiplying until it reaches  n - \left( n - 1 \right) = 1 . What you are saying is, for n=5, it goes till n-4. In general, it goes till n-(n-1). But this is just 1. It's equivalent. Concisely, it is$$ n! = ...

1

Suppose you want to find the number of ways to partition a set of n elements into k subsets or less, all of these non-empty and without the order of the partitions mattering. Then this is the same as $\sum_{j=1}^k S(n,j)$ where $S(n,j)$ denotes the number of way so partition a set of n elements into j subsets without the partitions being "labelled". the ...

1

When calculations involve large factorials, the use of Stirling approximation for n! is very convenient. In your case, you compare n! to n^(n/2). We can take logarithms of both sides and use the fact that Stirling approximation gives log(n!) close to n log(n) - n; the logarithm of the second term is simply n log(n) / 2. Using this approximation, you find ...

1

To identify the $c_n$, look up the definition of MacLaurin series. This will tell you how $c_n$ relates to $f^{(n)}(0)$. To figure out the radius of convergence, fix $x$ and use the ratio test. This will give you $|x|<R$. (You have to figure out $R$.) After you do this, substitute $x = R$ and $x=-R$ into the series to determine whether or not the ...

1

Your proof is nearly complete. For part (II), I would suggest that instead of concluding that $d=1$, conclude that the assumption for this part (that $d\nmid p$) contradicts the result that $d\mid 1$, therefore that this case leads to a contradiction and cannot occur. Then conclude that the result from part (I) is the only logical result, which is that ...

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