Tag Info

New answers tagged

3

The proof is nearly correct, but induction is unnecesary: $$\frac{1}{n} + \frac{1}{n+1} +\ldots + \frac{1}{2n} \geq \underbrace{\frac{1}{2n} + \frac{1}{2n}+\ldots +\frac{1}{2n} \frac{1}{2n}}_{n\text{ times}} = n\frac{1}{2n} = \frac{1}{2}$$


6

Take a look at the first few cases to get an idea what should happen. The first claim is $\frac11+\frac12\geq\frac12$, the second one is $\frac12+\frac13+\frac14\geq\frac12$, the third one is $\frac13+\frac14+\frac15+\frac16\geq\frac12$. So to get from $\frac1n+\dots+\frac1{2n}$ to $\frac1{n+1}+\dots+\frac1{2(n+1)}$ you need to subtract $\frac1n$ and add ...


1

Hint. I would suggest using congruence notation from the start. We have $$L\equiv a_1(2B)+B\pmod{4B^2}$$ and so $$L^2\equiv a_1^2(4B^2)+2a_1(2B)B+B^2\equiv B^2\pmod{4B^2}\ .$$ Since $B^2<4B^2$, the last two digits of $L^2$ are $b_1,b_0$ where $$B^2=b_1(2B)+b_0\ .$$ We know that there will be only one possibility for $b_1,b_0$ within the range ...


0

Continuing from Daniel Fischer's comment: $\sqrt{n+1} - \sqrt{n} \leqslant \frac{1}{\sqrt{n+1}} \leqslant 2(\sqrt{n+1}-\sqrt{n})$ Lets focus on the LHS: Lets assume $\sqrt{n+1} - \sqrt{n} \gt \frac{1}{\sqrt{n+1}}$ This implies: $n+1 - \sqrt{n^2+n} \gt 1 \rightarrow n\gt\sqrt{n^2+n}\;\; \forall n\geq1$ However, $n=1\rightarrow 1\gt\sqrt{2}$ which is ...


1

\begin{align*} \sum_{i=0}^\infty \sum_{j=0}^i \frac{(-1)^j}{j!} \prod_{k=0}^i (x-k) &= \sum_{i=0}^{\color{red}{x-1}} \sum_{j=0}^i \frac{(-1)^j}{j!} \prod_{k=0}^i (x-k) \\ &= x! \sum_{i=0}^{x-1} \sum_{j=0}^i \frac{(-1)^j}{j!(x-i-1)!} \\ &= x! \sum_{i=0}^{x-1} \sum_{j=0}^{x-i-1} \frac{(-1)^j}{j!\,i!} &&\text{(reindex $i:=x-i-1$)} \\ ...


0

Here is a start. We write the product as $$ \prod_{j=0}^{i}\left[ (x-j)\right] = \frac{x!}{\Gamma(x-i)}. $$ The sum $S$ becomes $$ S = x!\sum_{i = 0}^{\infty}\sum_{j=0}^{i}\frac{(-1)^j}{j!} \frac{1}{\Gamma(x-i)}=x!\sum_{i = 0}^{x-1}\sum_{j=0}^{i}\frac{(-1)^j}{j!} \frac{1}{\Gamma(x-i)} $$ since the gamma function $\Gamma(x-i)$ will start having poles ...


1

Is induction on $x$ acceptable? Because: $\sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] \prod_{j=0}^{i}\left[ (x+1-j)\right] \right] =\sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] \prod_{j=-1}^{i}\left[ (x-j)\right] \right] =\sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] ...


1

I think that your formula is a particular case of the Newton interpolation formula: Let $f(n)$ a fonction on $\mathbb{N}=\{0,1,\cdots\}$, put $\displaystyle a_n=\sum_{k=0}^n(-1)^k \binom{n}{k}f(n-k)$, and $\displaystyle g(x)=\sum_{n\geq 0}a_n\binom{x}{n}$, then we have $g(m)=f(m)$ for all $m \in \mathbb{N}$. (Also, look at your formula: for $i=0$, we get ...


0

Let $m=\min\{a/b,c/d\}$. This means that $$ m \le \frac ab \qquad \text{and} \qquad m\le \frac cd,$$ which is equivalent to $bm\le a$ and $dm\le c$. Thus we get $$a+c\ge bm+dm=(b+d)m$$ which is equivalent to $$\frac{a+c}{b+d}\ge m.$$ The proof of the inequality for maximum is similar. (Note that in all steps, where we multiplied the inequality by some ...


0

The induction on $k$ is standard: You can start with $k=1$ (we then have one set and the statement is trivially true). Assume truth for $k \ge 1$. For $k+1$, write $U_0 \cap \ldots \cap U_{(k+1)-1}$ as $(U_0 \cap \ldots U_{k-1}) \cap U_k$, and apply the hypothesis for the left hand side, and the given base property for the conclusion. To check we have a ...


2

I think what your professor had in mind is the following: one can prove "by induction" that $f'(a)=f''(a)$ for all $a\in A$, just by noting that if the statement holds for all $b<a$, then it holds as well for $a$, by definition. What you did is in fact more: you justified that such a reasoning is indeed correct, by considering the smallest $a$ such that ...


2

Once you get the first two steps, it is straightforward. Note that $$a_1a_2 \leq \left[\frac{a_1+a_2}{2}\right]^2$$ and $$(a_1a_2)(a_3a_4)\leq\left[\frac{a_1+a_2}{2}\right]^2\left[\frac{a_3+a_4}{2}\right]^2 = \left[\left(\frac{a_1+a_2}{2}\right)\left(\frac{a_3+a_4}{2}\right)\right]^2\\ \leq ...


0

The trick is to take advantage of the fact that the number of elements is a power of $2$ by splitting the factors into two equal parts and using the induction hypothesis on both halves. We want to show that $$(a_1a_2\cdots a_{2^{n+1}})^\frac{1}{2^{n+1}}\leq \frac{a_1+a_2+\ldots+a_{2^{n+1}}}{2^{n+1}}.$$ On the other hand, by the induction hypothesis we ...


2

This is known as the Faulhaber's formula: http://en.wikipedia.org/wiki/Faulhaber%27s_formula


1

It is a matter of doing things in an orderly manner. Yes, this covers all cases: either the image is contained in $[k]$, or it maps to $k+1$. Induction is made over $k$; not $m$. Careful. This is wrong. Induction is being made over $k$, and your induction hypothesis is that if $[m]\to [k]$ is an injection, $m\leqslant k$. You don't know anything about ...


0

As MathFacts suggested, using Stirling approximation for $n!$ could help. Limited to the very first terms, this approximation write $$n!\simeq n^n \sqrt{2 \pi n}e^{-n}$$ So $n! < n^n$ reduces to $$1 \lt\sqrt{2 \pi n}e^{-n}$$ which is obviously true for any $n \gt 2$.


0

$$(n+1)!$$ $=$ { by definition of the factorial } $$(n+1)\ n!$$ $<$ { by the recurrence hypothesis } $$(n+1)\ n^n$$ $<$ { by monotonicity of the $n^{th}$ power } $$(n+1)(n+1)^n.$$ $=$ { by distributivity of exponentiaition over multiplication } $$(n+1)^{n+1}.$$ And $$3!<3^3.$$


5

Use the induction method: First, take $n=3$, $3! = 6$ and $3^3 =27$, $3! < 3^3$. Second, assume the inequality holds for $n = K$, $K \in \mathbb{N}$, $K>3$, i.e. $K! < K^K$. Then consider $n= K+1$, $(K+1)! = (K+1) K! < (K+1) K^K < (K+1) (K+1)^K = (K+1)^{K+1} $, which is $(K+1)! < (K+1)^{K+1}$. Proved.


1

We know that $n!<n^n$ for some $n$, via our inductive hypothesis. We want to show that $(n+1)!<(n+1)^{n+1}$. Your first step is good, multiplying both sides of our inductive hypothesis by $n+1$ to get $(n+1)!<(n+1)n^n$. But $n^n<(n+1)^n$ (we can assume this, if not, it is very easy to prove), so $(n+1)(n^n)<(n+1)(n+1)^n$ and we have that ...


3

Via induction it's a bit tiresome but Base case $n=2$, $2!=2<4=2^2$ is pretty straightforward. Then multiplying both sides by $n+1$ gives $$(n+1)!< (n+1)n^n$$ Considering $$(n+1)n^n < (n+1)(n+1)^n=(n+1)^{n+1}$$ so by induction we are done. Again, a direct proof is infinitely easier, for $n\ge 2$, so I include it for comparison's sake. ...


0

Proof: by mathematical induction Choose any positive real number a which is smaller than 1, then 0 Because of (1), we conclude that 0 Good luck


1

$0 < a < 1 \ \Rightarrow \ 1 = a + x$ with $x > 0$. Thus, $$ 1 = 1^n = (a + x)^n = a^n + \sum_{k=0}^{n-1}{n \choose k}a^kx^{n-k} \geq a^n \quad \Rightarrow \quad a^n \leq 1 $$


2

Yes, you want to show that given $a^n\le 1$, then $a^{n+1}\le 1$. Well since $a>0$, we know that $a^{n+1}\le a$. But $a<1$. So we have $a^{n+1}\le a\le1$ as desired. This proof would clearly not work if $a$ were not less than $1$.


2

Lemma: If $0<a<1$ I claim for any $b>0$ that $0<ab<b$ Proof: $b(1-a)$ is a product of positive numbers hence is positive. Corollary: $a^n<1\implies a^{n+1}<1$ when $0<a<1$ Proof: By induction, the base case being given, then let $b=a^n$ in the lemma. Alternatively, a direct proof: Write $$a^n-1=(a-1)(a^{n-1}+a^{n-2}+\ldots ...


1

Seat one person at a (circular) table: $P(1) = 1 (=0!)$. Seat the second person at the table. There's only one place for them to go, so $P(2) = 1(=1!)$. Seat the third person at the table. That person can be seated with Person 1 on his left, or Person 2 on his left. So $P(3) = 2 \cdot P(2) = 2(=2!).$ Seat the fourth person. That person can be seated ...


2

If you leave out the $4n$-step, you only have to see that $$k^2 > 2k+1 \qquad\forall\ k>5$$ This is rather simple to see since $2k+1 < 3k < k\cdot k = k^2$ It occurs to me that that $4n$ was supposed to say $4k$ wich is fine and works just as well as the $3k$-term does in my alternative.


0

Induction problems like this can be done mechanically by telescopy. Rewriting $\,f(n) = 2^n-n^2\,$ as a telescopic sum of its differences makes its positivity obvious, because each summand is $\color{#c00}{\ge 0}.$ $$\displaystyle\begin{eqnarray}n\ge 5\ \ \Rightarrow\ \ \ f(n) &=&\! f(5)\,+ \sum_{\large k\,=\,5}^{\large n-1}\ (f(k\!+\!1)-f(k))\\ ...


2

Inductive hypothesis: For $n = k$, $$\color{blue}{2^k \geq k^2},\quad k \geq 4.$$ $$2^{k+1} = 2\cdot \color{blue}{2^k} \geq 2(\color{blue}{k^2}) \geq k^2 + k^2 \geq k^2 + 2k + 1 \overset{\large k>2} = (k+1)^2$$


0

$P(k)+Q(k) = P(k+1)$. You need to find Q(k), and show that $9\mid Q(k)$


2

A non-inductive proof. The usual way to define $a\leq b$ in the natural numbers is to say $a\leq b$ if there is a natural number $c$ such that $a+c=b$. Now, $n+n=1\cdot n + 1\cdot n = (1+1)n=2n$, so $n\leq 2n$.


5

Using the inductive hypothesis, $\color{blue}{n \leq 2n}$, we know that $$\color{blue}{n}+1\leq \color{blue}{2n} +1 \leq 2n+2 = 2(n+1)$$


2

Clearly, $n^n > n!$ for $n>1$ and so $n^{4n} > (n!)^4$. Therefore, we only need to prove that $3^{n^2} \ge n^{4n}$, or equivalently, $3^n \ge n^4$. This is true for $n \ge 8$. For $n <8$, we just verify explicitly that $3^{n^2} > (n!)^4$.


5

The induction-step should be pretty easy: Assume $\displaystyle3^{n^2}>(n!)^4$ Prove $\displaystyle3^{(n+1)^2}>(n+1)!^4$: $\displaystyle3^{(n+1)^2}=3^{n^2+2n+1}$ $\displaystyle3^{n^2+2n+1}=3^{n^2}3^{2n+1}$ $\displaystyle3^{n^2}3^{2n+1}>(n!)^43^{2n+1}$ $\displaystyle(n!)^43^{2n+1}=\frac{(n+1)!^4}{(n+1)^4}3^{2n+1}$ ...


1

Here is a way to derive this result. By the binomial theorem, $$(1+x)^n =\sum^{n}_{k=0}\binom{n}{k}x^k$$ Differentiate both sides. $$n(1+x)^{n-1} =\sum^{n}_{k=0} k\binom{n}{k}x^{k-1}$$ Substitute $x=1$ $$n2^{n-1} =\sum^{n}_{k=0} k\binom{n}{k} =\sum^{n}_{k=1} k\binom{n}{k} $$


4

Observe that: $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$. Thus: $\displaystyle \sum_{k=1}^{n+1} k\binom{n+1}{k} = \displaystyle \sum_{k=1}^{n+1} k\binom{n}{k} + \displaystyle \sum_{k=1}^{n+1} k\binom{n}{k-1} = \displaystyle \sum_{k=1}^n k\binom{n}{k} + \displaystyle \sum_{k=0}^n (k+1)\binom{n}{k} = 2\displaystyle \sum_{k=1}^n k\binom{n}{k} + ...


1

Prove the base case for $n=2$. So we have $\overline{A_1 \cup A_2} = \overline{A_1} \cap \overline{A_2}$. Assume it is true for $n=m$; i.e., $\overline{A_1 \cup A_2 \cup \ldots A_m}$ $=\overline{A_1} \cap \overline{A_2} \cap \ldots \overline{A_m}$. Now, let $B = \overline{A_1 \cup A_2 \cup \ldots A_m}$. Then, $B =\overline{A_1} \cap \overline{A_2} \cap ...


2

See George Tourlakis, Mathematical Logic (2008), page 93 : 3.2.1 Metatheorem (Post's Tautology Theorem) : If $\Gamma \vDash_{TAUT} A$, then $\Gamma \vdash A$. Proof. It is most convenient to prove the contrapositive, namely, if $\Gamma \nvdash A$, , then $\Gamma \nvDash_{TAUT} A$ Some facts are needed : Claim One. There is an enumeration ...


3

If you need to use induction, Base case: Take $n=1$. Suppose $5\mid 2^1\cdot a = 2a$. Now make the case that it must follow that $5\mid a$. Your justification here will also apply in the inductive step. Inductive hypothesis: Let $n = k \in \mathbb N$. Then we assume $$5\mid 2^ka \implies 5\mid a.$$ Inductive step: We need to show that for $n = k+1$, ...


2

One approach is to prove that the $n$x$n$ matrix $$M_n = \begin{bmatrix} 1 & 1 & 0 & 0 & \dots & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & \dots & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & \dots & 0 & 0 & 0 \\ & & & & \vdots \\ 0 & 0 & 0 & 0 & \dots & 1 & 1 ...


1

To get a light on, you have to either flip it once or three times and three times requires flipping three switches in a row. Flipping a switch twice never makes sense, as it does nothing. If you flip three switches in a row, the middle light will be on and the two next to it will be off, so you have to switch the two switches next to those three. This ...


2

You can think of this as a problem in $F_2^n$, the $n$-dimensional vector space over the field of 2 elements $\{0, 1\}$. A vector in that space isa list of $n$ ones and zeros, so it corresponds to a set of lights being on or off; I'll call that a "state". You also have a way to change state: you can flip switch 2, which changes the state of lamps 1, 2, and ...


2

We need to show: $k^k\cdot (k+1)^2 > (k+1)^{k+1}$ for $k > 3$.But it is the same as proving: $\dfrac{(k+1)^2 }{k} > \left(\dfrac{k+1}{k}\right)^{k+1} \iff k+1 > \left(1+\dfrac{1}{k}\right)^{k}$. But this is true because: $k + 1 > 3 > \left(1+\dfrac{1}{k}\right)^k$, $\forall k > 3$


2

There is an easier way. Notice that: $$\sum_{r = 1}^n a + (r-1)d = \sum_{r = 1}^n a + \sum_{r = 1}^n rd - \sum_{r = 1}^n d = na + d\left (\sum_{r = 1}^n r\right) - nd $$ Now, just prove by induction that $$\sum_{r = 1}^n r = \frac{n(n+1)}{2}$$ which is much easier, and manipulate the previous expression to get what you need.


1

The $r$th term, $u_r=a+(r-1)d$ with $u_1=a$ be the first term & $d$ be the common difference If $\displaystyle S_n= \sum_{r=1}^nu_n=\frac n2[2a+(n-1)d]$ $\displaystyle\implies S_{n+1}=\displaystyle \sum_{r=1}^{n+1}u_n=S_n+u_{n+1}=\frac n2[2a+(n-1)d]+a+nd$ $\displaystyle\implies S_{n+1}=(n+1)a+d\cdot\frac n2(n-1+2)=\frac{n+1}2[2a+(n+1-1)d]$


-2

Proove 5^n - 1 is divisible by 4 5^k - 1 = 4t 5^k = 4t + 1 5^(k+1) - 1 5(5^k) - 1 5(4t + 1) - 1 20t + 5 - 1 4(5t - 1) <=====


3

We consider a case where the number $n$ is expressed as a sum of $m$ natural numbers. The number of ways to do so is given by the coefficient of $x^n$ in $$(x+x^2+x^3+...)^m$$ To illustrate this point, we look at a specific example, with n=4 and m=2. The expression is $$(x+x^2+x^3+x^4+...)(x+x^2+x^3+x^4+...)$$ There are $3$ ways to form $x^4$ in the above ...


1

What you're looking for is ordered tuples $(a_1,\ldots,a_k)$, $k=1,\ldots,n$ with $a_i>0$ such that $\displaystyle\sum_{i=1}^k a_i=n$. Now, an ordered tuple $(a_1,\ldots,a_k)$ with $a_i>0$ such that the sum is $=n$ is just a set of $k$ boxes with at least one ball inside, i.e. $n-k$ balls in $k$ boxes. This is known to equal ...


2

It happens that $$ A_k = \left(\frac{18}{125}\right)^k\binom{3k}{2k}\phantom{}_2 F_1\left(1,-k;1+2k;-\frac{3}{2}\right),$$ and a clever idea is to use the Stirling approximation together with the Gauss continued fraction for the hypergeometric function in order to give tight bounds for $A_k$, then prove $A_{k+1}<A_{k}$ for any $k$ big enough. ...


3

This isn't rigorous, and it may in fact be what motivates the question, but you can interpret the $A_k$'s as the probability that a biased coin that lands Heads $60\%$ of the time and Tails $40\%$ of the time will come up Heads at least two thirds of the time when tossed $3k$ times. Since $60\%$ is less than $2/3=66.666...\%$, you can expect this to become ...


5

What you really need is $2 − \frac{1}{k} + \frac{1}{(k+1)^2} \leq 2 − \frac{1}{(k+1)}$,



Top 50 recent answers are included