# Tag Info

## New answers tagged induction

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