Tag Info

New answers tagged

5

We may suppose that $a_{n+1}$ is the largest element in $(a_1,\ldots,a_{n+1})$ and $a_n$ is the smallest one. Thus $a_{n+1}\geq 1\geq a_n$. with this information and the induction hypothesis we have $$ a_1+\cdots+a_{n-1}+a_na_{n+1}\geq n $$ and since $(a_{n+1}-1)(1-a_n)\geq 0$ we have $a_n+a_{n+1}-1-a_na_{n+1}\geq 0$. Just add this inequality to the ...


2

Wlog. $a_{n+1}=\max\{a_1,\ldots,a_{n+1}\}$ and hence $a_{n+1}\ge 1$. Let $c=\sqrt[n]{a_{n+1}}$, and $b_i=ca_i$ for $1\le i\le n$. Then $b_1b_2\cdots b_n=a_1a_2\cdots a_nc^n=1$, hence by induction hypothesis $b_1+\cdots + b_n\ge n$. Then $$a_1+\cdots+a_n+a_{n+1}=c(b_1+\cdots+b_n)+a_{n+1}\ge cn+c^n.$$ Clearly, $f(1)=n+1$ and the derivative $f'(c)=n+nc^{n-1}$ ...


1

Start anywhere and assume you have some unspecified suffcient (i.e. you will never run out of fuel along the trip) amount $x$ of fuel in the tank initially. As you refill during the trip exactly as much as you consume, you will end up with the same amount $x$ of fuel after the full round. During the trip, the fuel continuously decreases, except at the ...


3

Hint: $$\tan(a+b)=\frac{\tan a+\tan b}{1-\tan a\tan b}$$ In your case, for the base case $n=1$, $$\tan\left(\arctan 1+\arctan\frac{1}{3}\right)=\frac{\tan(\arctan 1)+\tan(\arctan\frac{1}{3})}{1-\tan(\arctan1)\tan(\arctan\frac{1}{3})}=\frac{1+\frac{1}{3}}{1-\frac{1}{3}}=2$$So $\arctan 1+\arctan\frac{1}{3}=\arctan 2$.


0

It's probably a typo. The correct statement is perhaps $$ A=\pmatrix{1-q&p\\ q&1-\color{red}{p}} \ \Rightarrow\ A^n= \frac1{p+q}\pmatrix{p&p\\ q&q} + \frac{(1-p-q)^n}{p+q}\pmatrix{q&-p\\ -q&p} $$ or its transposed version, so that you are asked to determine the power of a stochastic matrix.


1

If this is true for all $n=1,2,3\ldots$ then $A=A^1$ must be eqial to $$A= \begin{bmatrix} 1-q && p \\ q && 1-q \end{bmatrix}=\frac{1}{p+q}\begin{bmatrix} q && p \\ q && p \end{bmatrix} + \frac{(1-p-q)^1}{p+q}\begin{bmatrix} p && -p \\ -q && q \end{bmatrix}$$ For the ellement in the upper left corner we have ...


0

Suppose the case $P(n)$ holds. That is, we have $$ 1 + 2^1 + 2^2 + ... + 2^n = 2^{n+1} - 1 $$ We want to show the case $P(n+1)$ is implied by $P(n)$. Notice $$ 1 + 2^1 + 2^2 + ... + 2^n + 2^{n+1} = 2^{n+1} - 1 + 2^{n+1} = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1$$ Hence $P(n) \implies P(n+1)$, and the problem is now solved by the principle of mathematical ...


0

Let $S_n=\sum_{j=0}^n 2^j$. Then, $$S_{n+1}=S_n+2^{n+1}=2^{n+1}-1+2^{n+1}=2^{n+2}-1$$


0

firstly, we can know it is true for n=1 and n=2,suppose when n=k, it is also true. it means that $(1+x)^k$>=1+kx.Thus,$$(1+x)^{k+1}=(1+x)^k\times(1+x)\ge(1+kx)(1+x)$$ Finally,(1+kx)(1+x)=1+kx+x+$kx^2$>=1+(k+1)x.


1

Once you get to $$(1+x)^n=(1+x)^{n-1}(1+x)$$ you have rearranged the expression in a form in which you can use the inductive hypothesis, because you can assume that $$(1+x)^{n-1}\ge 1+(n-1)x$$ You should substitute that information into the expression you have for $(1+x)^n$ and see where it gets you when you follow it through logically. So in comments ...


6

For all odd n it is true. $(a+b+c)^3=a^3+b^3+c^3+3(a+b)(b+c)(c+a)$. Now according to the hypothesis $a+b=0 $ or $c+b=0 $ or $a+c=0 $. Say $a+b=0 $ then substituting it is true for all odd n. Similarly we can check for all other cases.


0

You've missed the sign! $a - b + c$ is not $a - (b+c)$, or even $a + (b+c)$. Instead, it is $a + (c-b)$, or equivalently, $a - (b-c)$ or $a + (-b + c)$.


1

First step is just multiplying 2 to $2^{k-1}$ and $(k+2)$. And next step is done by adding $-2(k+2)$ and $k+1$. Then it becomes $-(k+3)$ which is $-((k+1)+2)$. I think you missed the sign. So, following is true. $$4-\frac{k+2}{2^{k-1}}+(k+1)\left(\frac12\right)^k=4-\frac{2(k+2)}{2^k}+\frac{k+1}{2^k}=4-\frac{(k+1)+2}{2^{(k+1)-1}}$$.


0

When you look at the second line notice that they have an extra $2$ in the numerator they multiplied by $1$, which can also be written as $1 = \frac{2}{2}$. So just for completeness: \begin{align*} &4-\frac{k+2}{2^{k-1}}+(k+1)(\frac{1}{2})^k \\ & = 4-1\cdot\frac{k+2}{2^{k-1}}+(k+1)(\frac{1}{2})^k \\ & = ...


0

Simpler: By the hypotheses, $0 < u_1 < 4$. If you define an auxiliary sequence: $$ v_n = 4 - u_n $$ I.e., $u_n = 4 - v_n$, you have: $$ v_{n + 1} = \frac{v_n}{6 - v_n} $$ If $0 < v_n < 4$, $v_{n + 1} > 0$. We need the maximal value of $\frac{v}{6 - v}$ in the range $0 < v < 4$. We see that: $$ \frac{\mathrm{d}}{\mathrm{d} v} \frac{v}{6 - ...


0

For the record, this is a Ricatti recurrence, as $5 \cdot 2 - 1 \cdot 4 \ne 0$. There are at least three solution ideas around, I like Mitchell's "An Analytic Riccati solution for Two-Target Discrete-Time Control", Journal of Economic Dynamics and Control 24(4), pp 615-622 (2000). Take: $$ u_{n + 1} = \frac{a u_n + b}{c u_n + d} $$ Define a new variable by: ...


1

What they mean is that you should observe that $$4-u_{n+1}=4-\frac{5u_n+4}{u_n+2}=\frac{4-u_n}{u_n+2}$$ From this it is clear that if $4-u_n>0$, then $4-u_{n+1}>0$ and the gap gets smaller, so $u_n$ is increasing (to $4$ very fast).


0

\begin{align*} 1&\le\left(\frac12\right)^0\\ 1&\le1\\ 1\cdot2\cdot3\cdot\ldots\cdot(k-1)&\le\left(\frac k2\right)^{k-1}\\ k!&\le\left(\frac{k+1}2\right)^k\\ \left(\frac k2\right)^{k-1}k&\le\left(\frac{k+1}2\right)^k\\ 2\cdot k^k&\le(k+1)^k \end{align*} Fourth row is what needs to be proven and 5, 6 are what is sufficient to prove. I ...


-1

Assume result holds that is $ 1 \cdot 2 \cdot ... \cdot (n-1) \leq ( \frac{n}{2} )^{n-1} $, then $$ 1 \cdot 2 \cdot ... \cdot (n-1)\cdot n \leq ( \frac{n}{2} )^{n-1} \cdot n \leq_{GM-AM} \left( \frac{ n + \frac{n}{2} + ... + \frac{n}{2} }{n} \right)^n = \left( \frac{ \frac{2n}{2} + \frac{n}{2} + ... + \frac{n}{2} }{n} \right)^n = \left( \frac{ ...


-1

This follows directly form the AM GM inequality.


0

Clearly holds for $n=1$. Assume that it holds for $n=k$, therefore 7 divides $9^k - 2^k$. Now prove for $n=k+1$: $9^{k+1} - 2^{k+1}= 9(9^k - 2^k) + 9(2^k)- 2(2^k)=9(9^k - 2^k)+7(2^k).$ Now clearly, 7 divides $7(2^k)$, and 7 divides $9^k - 2^k$ by our inductive step. This completes the proof.


3

Inductive step: $$9^{k+1}-2^{k+1}=9(9^k-2^k)+9\times2^k-2\times2^k=9(9^k-2^k)+7\times2^k$$


0

The two terms are equal. Let $x = (2n)^{\log_2(m)}$ and $y = m^{1 + \log_2(n)}$ $\begin{align}\log_2(x) &= \log_2\left((2n)^{\log_2(m)}\right)\\ &=\left(\log_2(m)\right) \cdot \left(\log_2(2n)\right) \text{ since } \log a^b = b\log a\\&=\left(\log_2(m)\right) \cdot \left(\log_2(2) + \log_2(n)\right) \text{ since } \log ab = \log a + \log ...


1

Assuming it holds for $n-1$ it suffices to show that $$\frac1{n^3}\le\frac1{n-1}-\frac1n=\frac1{n(n-1)}$$ which is obviously true. You should see that adding \begin{align*}\frac1{2^3}+\ldots\frac1{(n-1)^3}&\le\frac58-\frac1{n-1}\\ \frac1{n^3}&\le\frac1{n-1}-\frac1n\end{align*} yields $$\frac1{2^3}+\ldots\frac1{n^3}\le\frac58-\frac1n\!\!\!$$


1

To give you an example of a "failed" induction proof, let $P(k)$ be the proposition $k>k+10$. Now, let's "prove" this by induction. You assume $P(k)$ holds, i.e., $k>k+10$. Then, adding $1$ on both sides of the inequality gives $k+1>k+1+10$ which is precisely $P(k+1)$. So now you know that if $P(k)$ is (ever) true, then also $P(k+1)$ is true. ...


4

If $\displaystyle4^k>3^k+2^k,$ $$4^{k+1}=4\cdot4^k>4(3^k+2^k)=4\cdot3^k+4\cdot2^k>3\cdot3^k+2\cdot2^k$$


2

"All this statement covers is the case in which Darren is in the cabal." I think I would agree with this. "It does not cover the case in which Darren is not in the cabal." I think I would agree with this too, provided that you state it a bit more precisely: the statement does not permit any deductions if Darren is not in the cabal. However, in the ...


0

You know that Martyna is not in the cabal. Can Darren be in the cabal? The answer clearly can't be yes: if it were, then Martyna would be in the cabal. Since it can't be yes, it must be no.


0

You have to understand, semantically, what the implication means (this is the definition of implication): $$ p \rightarrow q \equiv \neg p \vee q $$ This means that either $p$ is true and $q$ is true or $p$ is false (keep in mind that this means that $p$ and $q$ could both be false--this is what the english usually doesn't correctly represent). Therefore ...


0

In this case, if D is in the cabal, then M is def in the cabal. But if M is not in the cabal, then M is not in the cabal. Why can we make this assumption? Because suppose M was not in the cabal and D was in the cabal. Then that means M would have to be in the cabal since D is in the cabal, which is a contradiction because we were supposing that M was not in ...


0

Your understanding is incorrect. Let us take a look at what the statement $A \implies B$ means. $$\text{$A \implies B$ means if $A$ occurs, then $B$ *has to occur*.} \tag{$\star$}$$ Now if we figure out that $B$ has not occurred, then we can conclude that $A$ has not occurred, since if $A$ had occurred then $B$ has to have occurred by $(\star)$.


1

Implication is a bit of a weird animal with regards to language and how we come to know implication outside of mathematics. A lot of students get tripped up on this early on. I'm of the opinion that it is best to think of the truth or falsity of an implication statement by considering when it is false. If you find the case when it is false, it must be true ...


0

$$(k+1)^3=k^3+3k^2+3k+1\quad=>\quad(k+1)^3-k^3=3k^2+3k+1\quad=>$$ $$=>\quad\sum_0^n(3k^2+2k+1)=\sum_0^n\Big[(3k^2+3k+1)-k\Big]=\sum_0^n\underbrace{(3k^2+2k+1)}_{\large(k+1)^3-k^3}-\sum_0^nk=$$ $$=(n+1)^3-\frac{n(n+1)}2=n^3+\underbrace{3n^2+3n}_{6\tfrac{n(n+1)}2}+1-\frac{n(n+1)}2=n^3+5\cdot\underbrace{\frac{n(n+1)}2}_{\Large{n+1\choose2}}+1.$$


1

Recall the following identities: $$\sum_{k=0}^n 1 = n+1$$ $$\sum_{k=0}^n k = \dfrac{n(n+1)}2$$ $$\sum_{k=0}^n k^2 = \dfrac{n(n+1)(2n+1)}6$$ And $$\sum_{k=0}^n (3k^2+2k+1) = 3 \sum_{k=0}^n k^2 + 2\sum_{k=0}^n k + \sum_{k=0}^n 1$$ Now plug in and obtain what you want.


1

When you write "for $i=1$", I think you mean "for $n=1$". $i$ is just an index, which varies over all $0,1,\dots,n$ for a fixed $n$, so you want to show that the claim holds for all $n$, not all $i$. Other than that it looks pretty good. EDIT actually I see a couple of very minor issues. Your general idea is right. We begin with the base case: suppose ...


0

This is not true. The sum starts with $2*3^{-1}$, so it includes a term $2/3$ for $k=0$, so the left side is not an integer and the right side is an integer. I'm doing this as an answer because I am annoyed at the number of "proofs" of something that is false.


1

So, let's make this semi-rigorous. I assume that you already know the fundamental principles of mathematical induction so I won't go into great detail. Also, I assume that the sum starts at k=1, otherwise the statement isn't true ($\frac{2}{3}\neq0)$. We're going to divide this inductive proof into two steps Step 1: Show that the statement is true when n=1 ...


0

For the inductive step, assume $\sum\limits_{k=0}^n\ 2*3^{k-1} = 3^n-1$. You now want to somehow express this assumption in the $(n+1)th$ case. Notice that $$\begin{array}{ccl} \sum\limits_{k=0}^{n+1}2*3^{k-1}&=&\sum\limits_{k=0}^n2*3^{k-1}+2*3^n\\ &=&3^n-1+2*3^n\\ &=&3^{n+1}-1 \end{array}$$ (The assumption is used in the second ...


0

$$\sum_{k=1}^n 2\times3^{k-1} = \sum\limits_{k=1}^n (3-1)3^{k-1}= \sum\limits_{k=1}^n (3^k-3^{k-1}) = 3^n-1$$ by telescoping sum.


1

$$\sum_{k = 0}^{n+1} 2 \times 3^{k-1} = \sum_{k = 0}^n 2 \times 3^{k-1} + 2 \times 3^n\\ = 3^n-1+ 2 \times 3^{n} = 3^{n+1}-1$$


0

We can prove this with another method: Using AM-GM inequality. We have $\prod_{i=1}^{n} (1 + a_i) \leq (\dfrac{n + a_1 + a_2 +...+ a_n}{n})^n < (\dfrac{n + \frac12}{n})^n = \sqrt{(1 + \frac{1}{2n})^{2n}} < \sqrt{3} < 2$. We can prove by induction that: $(1 + \frac{1}{n})^n < 3$ for all naturals $n$'s , and this is well-known.


5

Note that $$4^{n+1} = \underbrace{4 \cdot 4^n > 4 (3^n+2^n)}_{\text{From induction hypothesis}} = \overbrace{4 \cdot 3^n + 4 \cdot 2^n > 3 \cdot 3^n + 2 \cdot 2^n}^{\text{Since }4 > 3 \text{ and }4>2} = 3^{n+1} + 2^{n+1}$$ and you are done.


0

You wrote that $x_n$ is defined as $x_1=1$ and $x_k=3x_{k-1}+k$ for $k\geq2$. Hence the error is NOT the "$+1$" in the point you indicated: the mistake is when you write: $$ x_{k+1}=3x_k+k $$ in fact, according to definition, you here missed a "$+1$": $x_k=3x_{k-1}+k\Longrightarrow x_{k+1}=3x_k+(k+1)$. After this everything should be fixed.


2

The proposition is true in the first case. If the proposition is true in the first case, then it is true in the second case. If the proposition is true in the second case, then it is true in the third case. If the proposition is true in the third case, then it is true in the fourth case. If the proposition is true in the fourth case, then it is true in ...


0

Let $$I_n = \int_0^{\pi/2} \dfrac{\sin(2n+1)x}{\sin(x)}dx$$ We then have $$I_{n+1} - I_n = \int_0^{\pi/2} \dfrac{2 \sin(x)\cos(2(n+1)x)}{\sin(x)} dx = 2\int_0^{\pi/2} \cos(2(n+1)x) dx = 0$$ for $n \neq -1$. Hence, $$I_n = I_0 = \dfrac{\pi}2$$ Essentially, we are saying that $\dfrac{dI_n}{dn} = 0$, where the derivative is to be interpreted in discrete sense ...


1

One way to prove the result besides using induction is to use contour integration. $$ \int_{0}^{\pi /2} \frac{\sin(2n+1)x}{\sin x} \ dx = \frac{1}{4} \int_{-\pi}^{\pi} \frac{\sin(2n+1)x}{\sin x} \ dx = \frac{1}{4} \text{Im} \ \text{PV} \int_{-\pi}^{\pi} \frac{e^{i(2n+1)x}}{\sin x}$$ $$ = \frac{1}{2} \text{Im} \ i \ \text{PV} \int_{-\pi}^{\pi} ...


1

So the problem is, I think, to prove that the outlined algorithm computes $s(n) = \sum_{i=1}^n s_i$, for a 'list' $(s_1,\ldots,s_n)$. Yes, your base case appears correct: if $n=0$, then the list is empty, so $\sum_{i=1}^n s_i=0$ (a bit by convention) and this algorithm, too, returns $0$. Otherwise, let $n>0$. Assume that the algorithm correctly computes ...


0

I think you may be confused with what k should be. If you have m terms, then k = m-1. For example, if you have 3 terms 1, 4 and 7, k should be 2 not 3.


0

Looks good! You should add brackets in this sum $$ \sum_{n=0}^k (3n+1) $$ to clarify whether the $+1$ summand belongs to the sum.


0

Your answer looks just fine, although you changed the role that $n$ plays in your formula half-way through the post.



Top 50 recent answers are included