New answers tagged

0

The given inequality is equivalent with $$1+\cdots +\frac{1}{n-1}-\ln n < \gamma$$ It now follows by remarking that $$b_n=1+\cdots +\frac{1}{n}-\ln (n+1)$$ (which has the same limit $\gamma$ as $a_n$) is increasing. This being easy to see from the inequality $$\ln (1+\frac{1}{n})\leq \frac{1}{n}$$


0

$\displaystyle (\lim a_n) -a_n = \sum_{k=n}^\infty a_{k+1}-a_k = \sum_{k=n}^\infty \frac{1}{k+1} - \ln\left(1-\frac{1}{k+1} \right)$ Since $\forall x> 0, x-\frac{x^2}2\leq \ln(1+x)< x$, $$-\frac 12 \sum_{k=n}^\infty \frac{1}{(k+1)^2} \leq (\lim a_n) -a_n < 0$$ A standard integral estimate yields $\displaystyle \frac 12 \sum_{k=n}^\infty ...


1

Imagine the theorem you are trying to prove is a set of stairs and proving the theorem amounts to getting to the top of the stairs in this analogy. Proving the base case amounts to climbing the first step. Think of the inductive step as follows: if you manage to get yourself to the $n^{th}$ step, then you can get to the $(n +1)^{th}$ step. So if you can get ...


0

Suppose we show, for a range of values of $k$, that $S(k)\implies S(k+1)$ for any $ k$ in the range.. This does not imply that $S(k)$ is true for any $k$. For example,when $S(k)$ is $k=k+1$ then we can prove that $S(k)\implies S(k+1).$ If you can exhibit some $k_0\in N$ such that $S(k_0)$ is true, and if you can show that $S(k)\implies S(k+1)$ for any ...


1

As Angel's answer notes, an ancillary inequality will be of use here, namely $$ 2^n\leq(n+1)!,\qquad n\geq1\tag{1} $$ which may be easily proved as well using induction (here is the meat of the inductive proof for $(1)$): $$ 2^{k+1}=2^k\cdot2\leq(k+1)!\cdot2\leq(k+1)!\cdot(k+2)=(k+2)!. $$ Hence, $$ ...


1

Hint: It will be sufficient to show that $$\frac{1}{(n+1)!}\le\frac{1}{2^{n-1}}-\frac{1}{2^n}=\frac{1}{2^n}$$ which follows easily from the fact $$2^n\le (n+1)!\qquad n\ge 1\text{ integer}\tag{1}$$ Inequality $(1)$ holds since $2\le 1\cdot 2$ and $2< i+1$ for all $1<i\le n$.


0

Hint: Assuming the conjecture true, compute $\phi^n-\phi F_n$ for increasing $n$: $$\phi^1-\phi F_1=\phi-\phi=0,\\ \phi^2-\phi F_2=\phi^2-\phi=1,\\ \phi^3-\phi F_3=\phi^3-2\phi=\phi^3-\phi^2+\phi^2-2\phi=\phi^2-\phi=1,\\ \phi^4-\phi F_4=\phi^4-3\phi=\phi^4-\phi^3+\phi^3-\phi^2+\phi^2-3\phi=2\phi^2-2\phi=2,\\ \cdots $$ and the pattern seems to be ...


2

It is easy to show $\phi^n = \phi F_n + F_{n-1}$ by induction. We have $F_1=1,F_0=0$, so for $n=1$ we have to prove that $\phi=\phi+0$, which is true. Suppose it is true for $n$. Then we have $\phi^{n+1}=\phi^2 F_n+\phi F_{n-1}$. Using $\phi^2=\phi+1$ the lhs becomes $\phi F_n+F_n+\phi F_{n-1}=\phi(F_n+F_{n-1})+F_n=\phi F_{n+1}+F_n$, so the result is true ...


0

I think this gets a bit simpler if you look at phi. It has a very special property, namely that $$\phi^2 = \phi + 1 $$ Which you can generalize to n by induction since $$\phi^n = \phi^{n-1} * \phi $$


3

Let $P_n=\prod_{i=1}^{n} \frac {n+1}{2i-3}$. Consider the ratio: $$\frac {P_{n+1}}{P_n}=\frac {2n+2}{2n-1}\;\prod_{i=1}^n \left(\frac {n+i+1}{2i-3}\times \frac {2i-3}{n+i}\right)=\frac {2n+2}{2n-1}\;\prod_{i=1}^n\frac {n+i+1}{n+i}$$ $$=\frac {2n+1}{n+1}\times \frac {2n+2}{2n-1}=2\times\frac {2n+1}{2n-1}$$ And the induction hypothesis now completes the ...


4

$$\prod_{i=1}^{n+1}\frac{n+1+i}{2i-3}=\prod_{i=1}^n\frac{n+i}{2i-3}\cdot\frac{(2n+1)(2n+2)}{(n+1)(2n-1)}\stackrel{\text{Inductive Hypotesis}}=$$$${}$$ $$=2^n\color{red}{(1-2n)}\frac{(2n+1)\cdot2\color{green}{(n+1)}}{\color{green}{(n+1)}\color{red}{(2n-1)}}=2^{n+1}\left(-1-2n\right)=2^{n+1}(1-2(n+1))$$ Explanation under request of the first equality above: ...


0

Using the mentioned inequality we have: $$\left(\frac{n+1}{n}\right)^n < e \implies \frac{(n+1)^n}{e^{n+1}} < \frac{n^n}{e^n} \implies \left(\frac{n+1}{e}\right)^{n+1} < \left(\frac{n}{e}\right)^n(n+1) \le n!(n+1) = (n+1)!$$ This proves the left side of the inequality. Similarly: $$e < \left(\frac{n+1}{n}\right)^{n+1} \implies ...


2

To be proved: $\displaystyle \sum_{i=n}^{2n} \frac{i}{2^i} \leq n$ Base case: $n=1$, $\displaystyle \sum_{i=1}^{2} \frac{i}{2^i}=1 \leq 1$ which works. Assume that for some $n$, $\displaystyle \sum_{i=n}^{2n} \frac{i}{2^i} \leq n$ Consider, for $n+1$, $\displaystyle \sum_{i=n+1}^{2(n+1)} \frac{i}{2^i} \leq n+1$ $\displaystyle \sum_{i=n+1}^{2n+2} ...


0

My preferred definition of a non-empty, full binary tree is: Definition 0. A pointed magma is an ordered triple $(X,\bullet,\star)$, such that $X$ is a set, $\bullet$ is an element of $X,$ and $\star$ is a function $X \times X \rightarrow X$. Definition 1. Write $F$ for the initial pointed magma. The elements of $F$ are called non-empty full binary ...


3

Your desired inequality can be written as $0\leq (a-b)(a^n-b^n)$ this is true regardless which is bigger.


0

For example above, the question is asking you determine which amounts of postage can be formed using $4$-cent and $5$-cent stamps. Such that we know $4,5,8,9,10,12,13,14,15, \ldots$ can be formed using just $4$ cent and $5$ cent. Why for basis are we just using $12-15$ instead of using $4-9$? This problem appears to be taken from Kenneth H. Rosen's text ...


0

Comment on the Approach in the Question The inductive step needs to show $$ \begin{align} 2b_{n-1}-2b_{n-2}-1 &=2\left(2^{(n-1)/2}\sin\left(\tfrac{(n-1)\pi}4\right)-1\right)-2\left(2^{(n-2)/2}\sin\left(\tfrac{(n-2)\pi}4\right)-1\right)-1\\ &=2^{(n+1)/2}\sin\left(\tfrac{(n-1)\pi}4\right)-2^{n/2}\sin\left(\tfrac{(n-2)\pi}4\right)-1\\ ...


1

Since you have verified the base case, we proceed to the inductive case. Fix $n >2$ and suppose that for all $k <n$, $P(k)$ is true. We want to show that $P(n)$ is true. $$ \begin{aligned} b_{n}&=2b_{n-1}-2b_{n-2}-1\\ &=2\left((\sqrt{2})^{n-1}\sin\left(\frac{1}{4}\pi (n-1)\right)-1\right)-2\left((\sqrt{2})^{n-2}\sin\left(\frac{1}{4}\pi ...


2

Induction works fine. If $$a(n)+\sqrt3\cdot b(n)=\left(1+\sqrt3\right)^n\;,$$ then $$\begin{align*} \left(1+\sqrt3\right)^{n+1}&=\left(1+\sqrt3\right)\big(a(n)+\sqrt3\cdot b(n)\big)\\ &=a(n)+3b(n)+\sqrt3\big(a(n)+b(n)\big)\;, \end{align*}$$ and the last expression is equal to $a(n+1)+\sqrt3\cdot b(n+1)$ if if we set $$a(n+1)=a(n)+3b(n)$$ and ...


0

This may be informal, but just showing that the sequence is monotone decreasing would mean the first term is the upper bound for the sequence. We may rewrite the sequence in the following way $a_{n+1}=\frac{a_n}{2n+1}$. We can then see whether the sequence is infact monotone decreasing $a_n-a_{n+1}=a_n-\frac{a_n}{2n+1}=\frac{2na_n}{2n+1}$ We know $ ...


1

Let $I_n$ be the integral defined by $$\begin{align} I_n&=\int_0^1 x^n\sqrt{1-x}\,dx\\\\ &=\int_0^1 (1-x)^n \sqrt{x}\,dx \end{align}$$ Integrating by parts with $u=(1-x)^n$ and $v=\frac23 x^{3/2}$ reveals $$\begin{align} I_n&=\frac23 n\int_0^1 (1-x)^{n-1}\,x^{3/2}\,dx\\\\ &=\frac23 n I_{n-1}-\frac23 nI_n\\\\ &=\frac{\frac23 ...


0

Hint: Write $x^n\sqrt{1-x}$ as $x^{n-1}(1-(1-x))\sqrt{1-x}$. That gives: $$ I(n) = I(n-1) - \int_{0}^{1} x^{n-1}(1-x)^{3/2}\,dx. $$ Use integration by parts on the last integral, and it will reveal itself as a peculiar multiple of $I(n)$. The previous relation can so be rearranged in order to give a closed formula for $\frac{I(n)}{I(n-1)}$ in terms of $n$ ...


0

You want to show that $$ \frac{\sin\frac{nx}{2}\cos\frac{(n+1)x}{2}}{\sin\frac{x}{2}} +\cos((n+1)x)= \frac{\sin\frac{(n+1)x}{2}\cos\frac{(n+2)x}{2}}{\sin\frac{x}{2}} $$ which is the same as $$ \sin\frac{nx}{2}\cos\frac{(n+1)x}{2}+\sin\frac{x}{2}\cos((n+1)x)= \sin\frac{(n+1)x}{2}\cos\frac{(n+2)x}{2} $$ Set $s=nx/2$ and $t=x/2$; the relation becomes, after ...


1

Here is the induction step: it comes down to proving \begin{gather*}\frac{\sin \dfrac{nx}{2} \cos\dfrac{(n+1)x}{2}}{\sin\dfrac{x}{2}}+\cos(n+1)x=\frac{\sin\dfrac{(n+1)x}{2}\cos\dfrac{(n+2)x}{2}}{\sin(\dfrac{x}{2})}\\ \text{or}\qquad\sin\dfrac{nx}{2}\cos\dfrac{(n+1)x}{2}+\sin\dfrac{x}{2}\cos(n+1)x=\sin\dfrac{(n+1)x}{2} \cos\dfrac{(n+2)x}{2} \end{gather*} Now ...


2

Recall $$f_n (z) = \sum_{k=0}^n \binom{n}{k} z^k = (1+z)^n,$$ by the binomial theorem. Now observe for $0 \le m \le k \le n$, $$\begin{align*} \binom{k}{m}\binom{n}{k} &= \frac{k!}{m! \, (k-m)!} \cdot \frac{n!}{k! \, (n-k)!} \\ &= \frac{n!}{m! \, (k-m)! \, (n-k)!} \\ &= \frac{n!}{m! \, (n-m)!} \cdot \frac{(n-m)!}{(k-m)! \, (n-k)!} \\ &= ...


6

Suppose that you want to choose a committee from $n$ people so that this committee has a president and a vice-president. The smallest committee here would have just a president and a vice-president (two members). One way to find the number of ways to do this is to sort by committee size and sum them up (as they are ...


3

$$\sum_{k=2}^{n}k\left(k-1\right)\binom{n}{k}=\sum_{k=2}^{n}\frac{n!}{\left(k-2\right)!\left(n-k\right)!}=n\left(n-1\right)\sum_{k=2}^{n}\binom{n-2}{k-2}=\cdots$$


4

I'm not sure how to proceed with your induction proof. A more direct approach is to write: $$\begin{align}k(k-1)\binom{n}{k}&=k(k-1)\frac{n!}{k!(n-k)!}\\ &=n(n-1)\frac{(n-2)!}{(k-2)!(n-k)!}\\ &=n(n-1)\binom{n-2}{k-2} \end{align}$$


5

Consider the classical binomial identity under the form $$\sum _{k=0}^{n} {n \choose k}x^k=(1+x)^{n}$$ derivate twice, then replace $x$ by 1.


1

Thanks to @drhab & @RRL Indeed $f(n) - f(0) = a^n b^{n-n} - a^0 b^{n-0} = a^n - b^n $ As for the second part, the formula of the geometric sum: $S = \sum_{i=0}^n a^i = 1 + a + a^2 + ... + a^n$ If i take the sum and multiply it times $a$ I get: $S\times a = a + a^2 + a^3 + ... + a^{n+1}$ Then I sustract $S$ from $S \times a$ and solve for $S$: $(S ...


0

Take any $n$ element cover. The case $n=1$ is clear. Assume $n >1$. If no two intervals intersect each other, then notice that no $a_i$ or $b_i$ is covered, therefore $a_i ,b_i \in \mathbb R \setminus [a,b]$ for all $i$. But $[a,b]$ is covered so there has to be an $i$ such that $a_i < a < b < b_i$ so the RHS above is at least $b-a$. If there ...


1

Here is a direct proof: Since the $(a_k,b_k)$ form a cover of $[a,b]$ then for all $x \in [a,b]$ there is some $k$ such that $x \in (a_k,b_k)$. Hence $1_{[a,b]}(x) \le \sum_k 1_{(a_k,b_k)}(x)$ for all $x$. It is clear that both sides are integrable, hence $b-a = \int 1_{[a,b]}(x)dx \le \int \sum_k 1_{(a_k,b_k)}(x) dx = \sum_k \int 1_{(a_k,b_k)}(x) dx = ...


2

The base case is clear. Let $\{(a_i,b_i)\}_{i=1}^n$ be an open cover of $[a,b]$. Suppose the sets are not nested. Then there are two sets $(a_i,b_i)$ and $(a_j,b_j)$ with $a_i \leq a_j \leq b_i \leq b_j$. Without loss of generality we may assume $i=1, j=2$. Taking their union, i.e. forming $(a_1,b_2)$ we get a smaller open cover and the induction step tells ...


2

For the first part you can indeed use induction, but you can also do without: $$\left(a-b\right)\sum_{i=1}^{n}a^{i-1}b^{n-i}=\sum_{i=1}^{n}a^{i}b^{n-i}-\sum_{i=1}^{n}a^{i-1}b^{n+1-i}=\cdots$$ Just work this out.


2

Induction hypothesis (IH): For all $x\leq k$, assume $$\sum_{j=1}^x (4j-1) = x(2x+1)$$ in particular, $$\sum_{j=1}^k (4j-1)=k(2k+1)$$ Then \begin{align} \sum_{j=1}^{k+1} (4j-1) &= \left(\sum_{j=1}^k (4j-1)\right) + (4(k+1)-1)\\ &= k(2k+1) + 4(k+1)-1 \quad\quad (IH)\\ &= k(2k+1)+4k+3\\ &= 2k^2+5k+3\\ &= k(2k+3)+2k+3\\ &= ...


2

For Inductive Hypothesis: LHS: $\sum_{j=0}^{k+1}(4j-1)=(4*1-1)+(4*2-1)+ ... +(4*(k-1)-1)+(4*k-1)+(4*(k+1)-1)=k(2k+1)+(4*(k+1)-1)=2k^2+k+4k+3=2k^2+5k+3$ RHS: $(k+1)(2(k+1)+1)=(k+1)(2k+3)=2k^2+5k+3$ $\therefore$ LHS=RHS


1

Let $f(x) = 3 -{1 \over x}$ and note that $f$ is increasing for all $x>0$. Let $\phi(x) = f(x) -x$ and note that $\phi''(x) = -{2 \over x^3}$, hence $\phi$ is concave. Note that $\lim_{x \downarrow 0} \phi(x) = \lim_{x \to \infty} \phi(x) = - \infty$ and $\phi(1) >0$. It follows that there are exactly two points $x_1,x_2$ with $0<x_1 <1 < x_2 ...


2

Let's first show that the sequence $\{x_n\}$ is monotone. $x_1 = 1 \le 2 = x_2$. Assume that $0 < x_1 \le x_2 \le x_n \le x_{n+1}$. Notice that $f(x) = 3 - \frac 1x$ is non-decreasing on $(0,\infty)$ since $f'(x) = \frac{1}{x^2} > 0$. Then $x_{n + 1} = f(x_n) \le f(x_{n+1}) = x_{n + 2}$. Let's now prove that $x_n \in (0,3)$ for all $n$. Again, we ...


1

a) I think we can instead prove $1 \le x_n < 3$. Then $0 < x_n < 3$ holds. By induction, (i) $x_1 = 1 \in [1, 3)$. (ii) Assume $1 \le x_k < 3 \Rightarrow -1\le -\frac{1}{x_k} < -\frac{1}{3} \Rightarrow 1 \le x_{k+1}= 3-\frac{1}{x_k} < 3$ Thus $1 \le x_n < 3 \Rightarrow 0 < x_n < 3$. Use induction to prove $\{x_n\}$ is ...


1

Sure. If $n=2k+1$ then $n^2=4k^2+4k+1=4k(k+1)+1$ and either $k$ or $k+1$ is even, so $4k(k+1)$ is divisible by $8$.


0

As many users commented above, these sorts of fairly trivial questions are mainly given to students to increase their familiarity with Mathematical Induction.


0

As @Ethan Bolker mentioned in the comment to my post above : "Reaching something that is obviously true" is not a proof! Which is exactly what I did here. For anyone who would like to read further how I realized this, the comments of this question : Is this direct proof of an inequality wrong? help to clarify why this is the case.


2

We, as usual, assume that there is a solution $L_n=\alpha^n$ so we have $\alpha^{n+1}=\alpha^n+\alpha^{n-1}$ hence that $$\alpha^2=\alpha+1$$ It follows $$\begin{cases} \alpha_1=\frac{1+\sqrt 5}{2}\\ \alpha_2=\frac{1-\sqrt 5}{2}\end{cases}$$ Hence $L_n=(\frac{1+\sqrt 5}{2})^n$ and $L_n=(\frac{1-\sqrt 5}{2})^n$ are solutions. A general solutions is ...


2

The recurrence is $L_{n+1}=L_{n}+L_{n-1}$.Now I am using the characteristic equation of this above recurrence to solve the recurrence. So the characteristic equation of this above recurrence is as follows $\implies$ Put $L_{n}={r^n}$ and solve the equation $\implies ({r^2}-r-1)=0$ By solving this equation we get $r=\frac{1+_-\sqrt{5}}{2}$(+ and -). ...


1

As what you tagged, we prove it by induction. For $n=0$, then the result is trivial. Suppose that the result holds for some $n\ge 0$, then for $n+1$, \begin{align} &\frac{(n+1)!}{x(x+1)(x+2)\cdots[x+(n+1)]}\\ &\quad\quad=\frac{n!}{x(x+1)(x+2)\cdots(x+n)}\cdot\frac{n+1}{x+n+1}\\ ...


3

Multiply both sides by $x+k$ $$\frac{n!}{x(x+1)(x+2)\cdots(x+k-1)(x+k+1)\cdots(x+n)} = \frac{A_0 (x+k)}{x+0} + \frac{A_1 (x+k)}{x+1}+...+A_k+\cdots+ \frac{A_n (x+k)}{x+n}$$ and make the specification $x=-k$. Then $$ \frac{n!}{(-k)(-k+1)(-k+2)\cdots(-1)\cdot 1 \cdots (n-k)} = \frac{n!}{(-1)^k k!\, (n-k)!}=(-1)^k \binom{n}{k} =A_k. $$


0

If $v'=\frac pq v$, then $qv'=pv$ and therefore $$q \langle v',w\rangle = p\langle v,w\rangle $$ This shows your goal for positive rational multipliers. You need negative ones too, but it will be enough if you can can show $\langle -v,w\rangle = -\langle v,w\rangle$.


1

First, extend the statement from the natural numbers to the integers by negation, simple enough. Now use the statement for integers to prove it directly for rationals. No further induction is necessary. Proof: Let $v, w$ be vectors in $V$, let $p/q$ be a rational number. Then $\langle{p\over q}v, w\rangle = {q\over q}\langle{p\over q}v, w\rangle = {1\over ...


1

For every $n\in\mathbb Z$ you have three possible cases. Either $n=3k$ or $n=3k+1$ or $n=3k+2$ (for some $k\in\mathbb Z$). Let us consider each of these cases separately: If $n=3k$, then $n^2=(3k)^2=3(3k^2)$, which means $3\mid n^2$. If $n=3k+1$, then $n^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1$. This implies $3\nmid n^2$. If $n=3k+2$, then ...



Top 50 recent answers are included