# Tag Info

1

You are assuming $$n!>(n/e)^n$$ and you want to show $$(n+1)!>\left ( \frac{n+1}{e} \right )^{n+1}.$$ We want to manipulate both sides to look more like the statement that we have assumed. The left side is $(n+1)n!$. The right side is $\frac{n+1}{e} \left ( \frac{n}{e} \right )^n \left ( \frac{n+1}{n} \right )^n$. By the inductive hypothesis you ...

1

Let's show that $$(k+1)\left(\frac{k}{e}\right)^{\!k}>\left(\frac{k+1}{e}\right)^{\!k+1}$$ which is equivalent to $$\frac{k^k}{e^k}>\frac{(k+1)^k}{e^{k+1}}$$ that is $$e>\frac{(k+1)^k}{k^k}=\left(1+\frac{1}{k}\right)^{\!k}$$

1

$$(k+1)(k/e)^k=(k+1)k^ke^{-k}\\ =(k+1)^{k+1}e^{-k-1}e^1\left(\frac k{k+1}\right)^k\\ \geq(k+1)^{k+1}e^{-k-1}e/e$$ because $e>((k+1)/k)^k\to1/e<(k/(k+1))^k$. So the next rung of the inequality has been established.

2

It looks fine! There's really no particular need for induction, though, if you know that $x\mapsto 2^x$ is an increasing function. Instead, show that $$2^{n+1}=2^n+2^n=2^n+2^{n-1}+2^{n-1},$$ so since $n-1\ge0$ for all positive integers $n,$ we have $2^{n-1}\ge 2^0=1,$ so that $$2^{n+1}\ge 2^n+2^{n-1}+1,$$ from which the result follows. More generally, we ...

2

That works if you first prove (by induction) that all $a_n$ are positive. That will let you apply the ordering axiom as you stated. For an example of why you need them positive, $$5 \geq 4$$ $$-1 \geq -1$$ but it is not true that $$-5 \geq -4$$ Strictly speaking, you are appealing to a slightly stronger induction principle than the one which is usually ...

2

You might find Faà di Bruno's formula useful with $g(x)= \ln (x)$. Since $$g^{(j)}(x)=(-1)^{j+1}\frac{(j-1)!}{x^j}$$ we get $${d^n \over dx^n} f(\ln x)=\sum \frac{n!}{m_1!\,1!^{m_1}\,m_2!\,2!^{m_2}\,\cdots\,m_n!\,n!^{m_n}}\cdot f^{(m_1+\cdots+m_n)}(\ln x)\cdot \prod_{j=1}^n\left((-1)^{j+1}\frac{(j-1)!}{x^j}\right)^{m_j}$$ where the sum is taken over ...

3

Observation. We have $$y^{(n)} = \frac{1}{x^n} \sum_{i=1}^n a_{(n,i)} f^{(i)}(\ln x)$$ Where $a_{(n,i)}$ is the coefficient of $x^{i-1}$ in $$\prod_{k=1}^{n-1} (x-k)$$ I will skip the base since it is given in the problem. Assume that this is true for $n=k \ge 4$. I will prove it for $n=k+1$. From the induction hypothesis, we have $$y^{(k)} = ... 0 I'm not sure my first instinct would be to do induction. I'd simply think each n people shake hands with n -1 everyone else for n(n -1) handshakes if you count Ann's handshake with Bob separately from Bob's handshake with Ann. But since you don't and there are 2 people to a handshake it n(n-1)/2 handshakes. But since the problem is to do it by ... 0 This would normally be calculated as \pmatrix{n\\2} where n is the number of handshakes. We know the following:$$\pmatrix{n\\2}=\sum_{i=1}^{n-1}i$$With the latter, we use Gauss' Method to obtain the following:$$\frac{(n-1)([n-1]+1)}{2}\equiv \frac{(n-1)(n)}{2}$$Which matches your solution. In simpler terms, imagine drawing an arrangement of n ... 0 between 2 people there's only one handshake happens..@Aldon but I'm also not sure how to this prove, it's not n=n(n-1)/2 for sure. for n=2 number of handshakes is 1 for 3 it's 3 for 4 it's 6 for 5  it's 10 0 Suppose you k people shake hands. Your induction hypothesis then is that there are \frac{k(k-1)}{2} handshakes. Now suppose you have one more person, so you have k+1 people. This new person will shake hands with all the other k people there, so now the number of handshakes will be \frac{k(k-1)}{2} + k. But if your general claim about the number of ... 0 One way to do this is by drawing n number of points and connecting all the points together using lines; the number of lines drawn would be the number of handshakes needed. For example for 2 points, in order to connect them you'd need a single line. For 3 points A, B, and C, you'd need one line to connect A to B, a second line to connect B ... 0 n odd means there is a k such that n = 2k+1, so n^2 -1 = (2k +1)^2 - 1 = 4k^2 + 4k, so ... (no need for induction). n^3 - n = n(n^2 - 1) = n(n - 1)(n+1). Of three consecutive integers, one is divisible by 3, and 1 or 2 are divisible by 2, so... (again no need for induction). 0 These two questions are proved in an identical fashion, so I'll give a brief overview of how to do the first one. It would be much more helpful if you mentioned where you're getting stuck. Base case (n=1). This is trivial to show Suppose that k is an odd integer (that k=2t+1 for some integer t), and that k^2-1 is a multiple of 4. In other words, this ... 0 \displaystyle \sum_{0 \le k \le 2n}(-1)^k \binom{4n}{2k} = \sum_{0 \le \frac{1}{2} k \le 2n} i^k\binom{4n}{k} = \sum_{0 \le k \le 4n}\binom{4n}{k}i^k = (1+i)^{4n} = [(1+i)^4]^n = (-1)^n 4^n.  3 Basic approach. There's probably an easier way to do this, but the way that comes to mind immediately is to use the binomial theorem on the expression$$ (1+i)^{4n}+(1-i)^{4n} $$where i = \sqrt{-1}. This will give you twice your summation. Then observe that$$ (1+i)^{4n} = \left[(1+i)^4\right]^n = (-4)^n  (1-i)^{4n} = \left[(1-i)^4\right]^n = ...

1

You have to show that : $S \subseteq A$. To do this, you have to follow the two-steps definition of $S$ : (i) $3 \in$; but $3$ is divisible by $3$. Thus : $3 \in A$. (ii) this is the iduction step. We assume the induction hypotheses, i.e. that if $x,y \in S$ such that $x+y \in S$, and $x,y \in A$, then also $x+y \in A$. But if $x,y \in A$, then ...

1

This is a proof by induction, showing that if $z\in S$ i.e. created from the recursive scheme, then $z\in A$. The induction is done over how many recursive steps were applied in order to create an element in $S$. Bellow is how the proof looks like if we do it carefully written out in multiple explicit steps. The point is that we are assuming $x$ and $y$ to ...

2

About your first question, you just have to observe that $R_k(n)$ is multiplicative beeing a Dirichlet product of multiplicative functions, and as a consequence so is $r_{k}(n)$, so you can compute it for a prime power a then multiply, $$R_k(n) = \prod_{p^j\vert\vert n} R_k(p^j)$$ For computing $R_k(p^j)$ we treat separately the divisor 1 for the rest of ...

0

Hint: $$(n+1)((n+1)+1)=(n+1)(n+2)=n(n+1)+2(n+1)$$

0

Claim: P(n): n(n+1) is even $\forall n \in \mathbb{N}$ Base case: P(0): 0(1) = 0. Since 0 can be written in the form 2t, t $\in \mathbb{Z}$, 0 is even. The base case holds. Alternative base case if you want to start at 1: P(1): 1(2) = 2. Since 2 can be written in the form 2t, t $\in \mathbb{Z}$, 0 is even. The base case holds. inductive hypothesis: ...

0

From $k^2$ + $3k$ + 2, you could do cases for k. Case 1: If k is even, then let k = 2c for some integer c. Then you get $(2c)^2$+ $3(2c)$ +2 , which could be written as 2(2cc) + 2(3c) +2 or 2(2cc + 3c + 1), which is even. Case 2: If k is odd, then let k = 2c+1 for some integer c. Then you get $(2c+1)^2$+ $3(2c+1)$ +2 , which could be written as $4c^2$ + ...

1

What you wrote in the second line is incorrect. To show that $n(n+1)$ is even for all nonnegative integers $n$ by mathematical induction, you want to show that following: Step 1. Show that for $n=0$, $n(n+1)$ is even; Step 2. Assuming that for $n=k$, $n(n+1)$ is even, show that $n(n+1)$ is even for $n=k+1$. [Added:] In Step 2, what you really need to ...

0

The induction hypothesis in this case is that $mirror(mirror(t))$ holds for the subtrees $l$ and $r$. Hence, we get $$mirror(mirror(Node(l,v,r))) = Node(mirror(mirror(l)),v,mirror(mirror(r))) = Node(l,v,r),$$ which is what we wanted to prove.

7

$$(\sum_{i=1}^n |x_i|)^2 = \sum_{i=1}^n |x_i|^2 + 2\sum_{1 \le i < j \le n} |x_i| |x_j| \ge \sum_{i=1}^n |x_i|^2$$

0

You can almost get the answer, albeit with some cheating. First, $(x+y)^n=x^n(1+(y/x))^n$, so we can reduce this to showing: $$(1+x)^n = \sum_{k=0}^n\binom{n}{k}x^k$$ $$(1+x)^{n+1}=(n+1)\int_{-1}^x(1+t)^{n}dt=\sum_{k=0}^n\binom{n}{k}\frac{n+1}{k+1}(x^{k+1}-(-1)^{k+1}).$$ $$\binom{n}{k}\frac{n+1}{k+1}=\frac{(n+1)!}{(k+1)!(n+1-(k+1))!}=\binom{n+1}{k+1}.$$ ...

2

We need some proposition depending on $n$ that we can prove by induction. In this case, it is $$P(n)\ \colon\ \sum_{i=1}^n i \geq \frac{n^2}{2}.$$ First check the base case: $$P(1)\ \colon\ 1\geq \frac{1}{2}.$$ This is true, so we have proved the base case $P(1)$. Next suppose that $P(n)$ is true, for some $n\geq 1$. We wish to prove that then $P(n+1)$ is ...

0

Hint: $\sum_{i =1}^n i \ge \frac {n^2} 2$ iff $2\sum_{i =1}^n i = (1 + .... + n) + (1 + ..... + n) \ge n^2$. What is $(1 + ...... + n) + (1 + ...... +n)$? Hint: addition is commutative and associative.

1

Here is an answer to the parts of your question: It is not possible to prove your statement by direct induction. I take this to mean the proof is only allowed use the induction hypothesis. Otherwise the question becomes incredibly vague. The reason why is given in the comments. An inductive hypothesis of $\sum\limits_{k=1}^n\frac{1}{k^2}<2$ is too weak ...

4

HINT: prove that $\frac{1}{k^2}\le \frac{1}{k(k-1)}$ for $k>1$

1

The question should specify that the sequence is increasing since $\{1,2,4,3,5\}$ is a counterexample. Let's prove this by induction. The base case of $a_1 = 1$ holds since $a_1^2 = a_1^3$. Now assume that $(a_1,\ldots,a_k) = (1,\ldots,k)$ for some $k$. Then we have that $(1+2+\cdots+k+a_{k+1})^2 = \Bigg(\dfrac{(1+k)k}{2}+a_{k+1}\Bigg)^2$. Also, we have ...

4

You just need to estimate the primes. We have $p_i\geq 2$.

0

Mathematical Induction is true for every well ordered set. $\mathbb{N}$ is a natural example of well ordered set, but we have induction in other sets like: $$W=\left \{ \alpha |\alpha <\epsilon_0 \right \}$$ and $\epsilon_0=\sup{\left \{\omega,\omega^{\omega},\omega^{\omega^{\omega},...} \right \}}$ is an ordinal number. See Transfinite induction for more ...

2

(for the purpose of this answer I assume $0\in\Bbb N$) This really depends on what exactly you are trying to prove. If you want that property $P$ holds for all $n\in\Bbb N$, then it is necessary to either start the induction with base case $n=0$, or to start it with base case $n=1$ and then verify $P$ for $0$ separately (which might not be at all trivial!). ...

1

$$a_n+1=2\left(a_{n-1}+1\right)=2^2\left(a_{n-2}+1\right)=...=2^{n-2}\left(a_{2}+1\right)=2^n$$ $$\therefore a_n=2^n-1$$

3

We use induction. Now, we already know that $a_1=\frac{a_2-1}{2}=\frac{3-1}{2}=1=2^1-1$. Assume that we already know the statement is true for $n=k$, i.e. we know $a_k=2^k-1$. Then, since $a_{k+1}=2a_k+1=2(2^k-1)+1=2^{k+1}-1$, we get that the statement is true for $n=k+1$ as well. This completes the induction.

0

Or we could just expand and rearrange\begin{align} 3^{3n+1}+2^{n+1} &= 3\cdot27^n + 2\cdot2^n \\ &= 3\cdot(25+2)^n + 2\cdot2^n \\ &= 3\left(5k+2^n \right) + 2\cdot 2^n \tag{Using Binomial Theorem}\\ &= 5\cdot k'+3\cdot2^n+2\cdot2^n \\ &= 5\cdot k'+5\cdot 2^n \\ \end{align} Hence proved

3

Perhaps the following will make it easier for you to understand. First, show that this is true for $k=3$: $2\cdot3+1<2^3$ Second, assume that this is true for $k$: $2k+1<2^k$ Third, prove that this is true for $k+1$: $2(k+1)+1=$ $2k+3=$ $\color\red{2k+1}+2<$ $\color\red{2^k}+2=$ $2^k+\color\green{2^1}<$ $2^k+\color\green{2^k}=$ ...

5

No, that is not a typo. What the author is saying is that since, by the assumption that $2k + 1 < 2^k$, one can substitute $2^k$ for $2k + 1$ in the equality $2k + 1 + 2 = 2(k + 1) + 1$ to find the inequality $2(k+1) + 1 < 2^k + 2$. Since $2^k + 2 < 2^k + 2^k = 2^{k+1}$, this inequality implies what you want to show.

1

Well, you did it already, but let me try to answer what they are asking. Let CorrectPoint($x_1,x_2,\ldots,x_{2n}$) denote the point that causes a win for $2n$ dots. First, CorrectPoint($x_1,x_2$) is equal to whichever of $x_1$ and $x_2$ is the red dot. Second, for $n\geq 2$ and given $(x_1,x_2,\ldots,x_{2n})$, first identify a pair $(x_i,x_{i+1})$, such ...

3

Here's a straight application of simple induction (not strong induction), twice: We want to prove $P(m,n)$ by induction over $n$. Thus we need to prove $P(m,0)$ and $P(m,n)\to P(m,n+1)$. But in order to prove $P(m,0)$ we use induction over $m$, so we need to prove $P(0,0)$ and $P(m,0)\to P(m+1,0)$. In symbols, this amounts to the following assertion: ...

3

You almost have a complete proof. The key point that you need to finish the proof is that if $n \ge 1$ then $\dfrac{1}{n+1} \le \dfrac{1}{1+1} = \dfrac{1}{2}$. Hence, your inductive step $P(n) \implies P(n+1)$ can be completed as follows: $$\sum_{k=1}^{n+1} \frac1k - 1 = \sum_{k=1}^n \frac1k + \frac 1{n+1} - 1 < \frac n2 + \frac 1{n+1} \le ... 1 So, we show the base case holds true (clearly since 3^3=3^3). So, we assume for our induction hypothesis that 3^k\geq k^3 and wish to show it follows also for k+1 when k\geq 3. (Keep in mind that because it isn't true for smaller values of k that the fact that k\geq 3 will likely play a role somewhere in the proof) We have: 3^{k+1}=3\cdot ... 0 Now you want to argue that 3k^3 \gt (k+1)^3 or 3 \gt (1+\frac 1k)^3 0 First notice that$$ 3^n \ge n^3 \;\; \Leftrightarrow \;\; n \ln{3} \ge 3 \ln{n} \;\; \Leftrightarrow \;\; \frac{\ln{3}}{3} \ge \frac{\ln{n}}{n}$$then,$$ \frac{d}{dn} \left( \frac{\ln{n}}{n} \right) = -\frac{\ln{n-1}}{n^2}$$and since the right hand side is negative for n\ge 3 the result follows. 2 Suppose for a fixed n that \color{blue}{\sum_{i=1}^n \binom{i}{2}= {n+1 \choose 3}}. Consider \sum_{i=1}^{n+1} \binom{i}{2}. Then$$\sum_{i=1}^{n+1} \binom{i}{2}= \binom{n+1}{2} + \color{blue}{\sum_{i=1}^n \binom{i}{2}} = \binom{n+1}{2} + \color{blue}{\binom{n+1}{3}}.$$Is the right hand side equal to \binom{(n+1)+1}{3}? If it is, then we've ... 1 It is true that this exercise can be answered without induction. But if you insist on it, your next step is: Assume as an inductive hypothesis that 4k^2+2k+1 is odd, and use this assumption to show that 4(k+1)^2+2(k+1)+1 is odd. 0 Consider the more general problem: For which a,b>0 do we have F(n) \le ab^n ? The natural induction argument goes as follows:$$ F(n+1) = F(n)+F(n-1) \le ab^n + ab^{n-1} = ab^{n-1}(b+1) $$This argument will work iff b+1 \le b^2 (and this happens exactly when b \ge \phi). So, in your case, you can take a=1 and you only have to check that b+1 ... 0 For n = 1, see that it holds: 1 = F_1 < 2^1. Assume that F_k < 2^k. Since F_{k+1} = F_k + F_{k - 1} < 2^k + 2^{k - 1} < 2^{k + 1}, as desired. 3 There is no need to use induction in this proof. Once you have gotten to 4k^2 + 2k + 1, we can note that$$ 4k^2 + 2k + 1 = 2(2k^2 + k) + 1 = 2l + 1  for $l = 2k^2 + k$. Since $2l$ is even, $2l+1$ must be odd, and you have shown your statement for all even numbers without having to resort to induction.

Top 50 recent answers are included