# Tag Info

## New answers tagged induction

2

You can also prove it combinatorially. First multiply by $(n+1)!$ and simplify a little to get the equivalent identity $$1\cdot3\cdot5\cdot\ldots\cdot(2n-1)\cdot 2^n=n!\binom{2n}n\;.\tag{1}$$ I claim that each side of $(1)$ is the number of ways to divide a pool of $2n$ chess players into $n$ pairs and assign one member of each pair to play the white ...

2

Note that when $m\ge 2$ and $m^2 = n$, $$(m+1)^2 = m^2 + 2m + 1 \le 2m^2 +1 \le 2m^2 + 2 = 2n+2.$$

0

$$A=\lim_{x\to 0^+}\frac{f(x)-f(0)}{x-0}=\lim_{x\to 0^+}\frac{e^{-1/x}}{x}$$ for this let $\frac{1}{x}=u$ then $$A=\lim_{x\to 0^+}\frac{e^{-1/x}}{x}=ue^{-u}=\lim_{u\to +\infty}\frac{u}{e^u}=0$$ Note that $e^x=\sum \frac{x^n}{n!}$ thus $e^{-1/x}=\sum \frac{{(\frac{-1}{x})}^n}{n!}$ so $$\frac{e^{-1/x}}{x}=\sum \frac{(-1)^n}{x^{n+1}n!}$$

0

$\lim_{x \to 0+} \frac{e^{-1/x}}{x} = \lim_{x \to 0+} \frac{1/x}{e^{1/x}}$ so we just apply L'Hopitals rule to get $0$ as the answer. Now use induction to prove that $f^{(n)}(x)/x = \frac{e^{-1/x}}{P_n(x)}$ where $P_n(x)$ is a polynomial of degree $n$.

0

What have you tried so far? What are you planning to use as your base case/cases and induction step? Edit: Your idea of 1,1 is on the right track, but think of the base case as being more general. The base case can be any case where the answer is easy to test, and where you can't induct any lower. Basically these are the endpoint/edge cases, For example, ...

3

By multiplying both numerator and denominator by $\;2\cdot 4\cdot 6 \cdot \ldots \cdot (2n)=2^nn!$ we get \begin{align} \frac{1\cdot 3\cdot 5\cdot \ldots \cdot (2n-1)}{2^n(n+1)!}&=\frac{1\cdot \color{red}{2}\cdot 3\cdot \color{red}{4}\cdot 5\cdot \color{red}{6}\cdot \ldots \cdot (2n-1)\cdot\color{red}{2n}}{2^n(n+1)!\cdot \color{red}{2^nn!}}\\ ...

0

Check this out..I believe this will be a good start. http://www.shsu.edu/~ldg005/data/mth164/F2.pdf

0

Doesn't this imply that (a−b)∣(an−bn)(a−b)∣(an−bn) as an−1+an−2b+⋯+bn−1an−1+an−2b+⋯+bn−1 is clearly an integer? This obviously isn't a proof by induction, but is there anything wrong with taking this approach to prove this result, other than the fact that it isn't what is being asked? Well, the only way to make that proof complete is to handle that ...

1

Hint: Write $\;a^{n+1}-b^{n+1}=a(a^n-b^n)+ab^n-b^{n+1}$ and apply the induction hypothesis. However, the most natural way consists in proving first the formula: $$1-x^n=(1-x)(1+x+\dots+x^{n-1})$$ by a very easy induction (actually it is one of the most illuminating examples of induction when one wants to explain it to beginners). Then set $x=\dfrac ab$. ...

1

Write $a^{n+1}-b^{n+1}=(a+b)(a^n-b^n)-ab(a^{n-1}-b^{n-1})$ and then apply the induction hypothesis.

0

HINT: multiplying $$n!>n^2$$ by $n+1>0$ we get $$(n+1)!>n^2(n+1)$$ and now you have to show that $$n^2(n+1)>(n+1)^2$$ which is easy.

0

$4!=24>16=4^2$, so the basic step holds. Then: $$(n+1)! = (n+1) n! \color{red}{>} (n+1) n^2 > (n+1)(n+1) = (n+1)^2$$ and we are fine. We used the inductive hypothesis in $\color{red}{>}$.

0

A proposition is true when $n=1$. If it is true when $n=1$, then it is true when $n=2$. If it is true when $n=2$, then it is true when $n=3$. If it is true when $n=3$, then it is true when $n=4$. If it is true when $n=4$, then it is true when $n=5$. If it is true when $n=5$, then it is true when $n=6$. and so on${}\,\ldots$ If this sequence can be ...

0

$\bf Definition:$ Inductive set. An inductive set is a set S that satisfies: $1\in S$. $k\in S\implies k+1\in S$. $\bf Definition: \Bbb N$ $\Bbb N$ is the set that satisfies: $\Bbb N$ is inductive. If $H$ is inductive, then $\Bbb N \subseteq H$. Consider now, some proposition $P(n)$. Let $T=\{n\in \Bbb N: P(n)\}$ be the set of $n\in \Bbb N$ that ...

1

Let prove the following theorem: 1) $A(0)$ true, 2) For all $n$ we have that $A(n)$ true $\implies A(n+1)$ true. Then $A(n)$ is true for all $n$. Let denote $$\mathcal W=\{n\mid A(n)\ \text{ is false}\}.$$ Suppose by contradiction that $A$ is not true, i.e. that $|\mathcal W|\neq\emptyset$. Since $\mathcal W\subset \mathbb N$ and that ...

0

I'm not sure what you are asking. There are two things involved: Intuition. You prove that your statement is true for $n=1$, and then from this you show it's true for $n=2$, from that for $n=3$ etc., just you do all these steps in one step. Axiom of induction. One of its versions is $$\forall P \Bigl( \Bigl( \forall n \bigl( \forall m (m<n \implies ... 2 You have proved it for k=2. Let's suppose that it holds for k, we'll show it holds for k+1. Let q=(a+bi)^k. Note first that$$(a+ib)^{k+1}=q^k(a+bi)=aRe(q)-bIm(q)+(aIm(q)+bRe(q))i $$Now: A^{k+1} = \begin{bmatrix} a & -b \\ b & a \end{bmatrix}^{k+1}=\begin{bmatrix} a & -b \\ b & a \end{bmatrix}^{k}\begin{bmatrix} a & -b \\ b ... 1 Hint: The easier way is to prove that$$J=\begin{bmatrix} 0 & -1 \\ 1 & 0\end{bmatrix}$$has the property J^2=-I and you are trying to prove that A=aI+bJ is "like" a+bi. Then the induction step is much cleaner. 2 There is a field isomorphism \eta :\Bbb C\to F where F is the set of matrices M(a,b)= \begin{pmatrix} a&b\\-b&a\end{pmatrix},a,b\in\Bbb R under usual matrix sum and multiplication that sends a+bi to M(a,b) and your claim follows from this. 2 2 \times3^0+2 \times 3^1+...+2 \times 3^{n-1}+2 \times 3^n=3^n-1+2 \times 3^n=3^{n+1}-1 Hope this helps. 4 So we assume that$$2\cdot3^0+2\cdot3^1+2\cdot3^2+...+2\cdot3^{k-1}=3^k-1$$Now add 2 \cdot 3^{k} to both sides:$$ 2\cdot3^0+2\cdot3^1+2\cdot3^2+...+2\cdot3^{k-1}+2\cdot 3^{k}=2\cdot 3^k +3^k-1 = 3 \cdot 3^{k}-1 = 3^{k+1}-1, $$which is of the same form as the n=k case with k replaced by k+1, and hence the statement is true for n=k+1. 1 Try writing the inequality the other way: 2^{n+1}>n^2+2. It is clear this is not true for n=0, but try to prove it is true for n\geq 1. For n=1, we have that 2^{n+1}=2^{2}=4>3=1^2+2=n^2+2. Now show the inequality holds for when n=2: we have 2^{3}=8>6=2^2+2, and this is true. Now try a proof by induction. I'll provide a brief sketch ... 1 The question was solved in comments. I am posting a CW-answer so that it does not remain unanswered. You can check that the inequality in the question if false even for very small numbers:$$ \begin{array}{|c|c|c|} \hline n & 2^{n+1} & n^2+2 \\\hline 1 & 4 & 3 \\\hline 2 & 8 & 6 \\\hline 3 &16 &11 \\\hline 4 &32 ...

1

Either you know the result on geometric series saying that $\sum\limits_{i=0}^{n} a^i =\frac{1-a^{n+1}}{1-a}$ which concludes your proof. Or, another way is to notice that $$f_2(n)=1+\sum_{i=0}^{n-1}f_2(i)=\left(1+\sum_{i=0}^{n-2}f_2(i)\right)+f_2(n-1)=f_2(n-1)+f_2(n-1).$$ And you should be able to conclude from here.

1

It is clear that $$1+\frac{1}{\phi}=1+\frac{\sqrt{5}-1}{2}=\frac{\sqrt{5}+1}{2}=\phi$$. Similarly $$1-\phi=1-\frac{\sqrt{5}+1}{2}=-\frac{\sqrt{5}-1}{2}=-\frac{1}{\phi}$$.

4

I am going to show $\qquad\frac{2n-1}{2n}\le\frac{\sqrt{3n-2}}{\sqrt{3n+1}},\quad$ which can be re-written as $$1-\frac{1}{2n}\le\sqrt{1-\frac{3}{3n+1}}\tag{1}$$ By squaring, we have ($1$) is equivalent to \begin{align} &&1-\frac{1}{n}+\frac{1}{4n^2}&\le 1-\frac{3}{3n+1}\\ \iff&&\frac{3}{3n+1}+\frac{1}{4n^2}&\le \frac{1}{n}\\ ...

1

Hint: For $m>n>0$, we have $$\frac1m<\frac1n.$$ In particular, for $m\in\Bbb N$, we have $$\frac{1}{9m^2}\leq\frac19.$$Can you take it from here?

1

For one thing: $$\frac1{9(N+1)^2}\space<\space\frac1{9N^2}$$ so: $$\frac1{9(N+1)^2}+ \frac2{3}\space<\space\frac1{9N^2}+ \frac2{3}\space<\space1$$

1

Hint By (repeated) Distributivity, we have : $[(\psi_1 \land \psi_2) \lor (\sigma_1 \land \sigma_2)] \equiv [(\psi_1 \lor \sigma_1) \land (\psi_1 \lor \sigma_2) \land (\psi_2 \lor \sigma_1) \land (\psi_2 \lor \sigma_2)]$. Thus, you have to simply "rearrange" the new disjunction of conjuncts (coming from the negation of the original conjunction of ...

1

All the $g_i$ are odd. If $(g_a,g_b)=d>1$ then there must be an odd prime $p$ which divides both $g_a$ and $g_b$. Assume $a>b$. Then $g_a=g_1\cdots g_b\cdots g_{a-1}-2$ which means that if $p\mid g_a ,p\mid g_b$ then $p\mid g_a- g_1\cdots g_b\cdots g_{a-1}$ which means $p\mid 2$ a contradiction.

1

If $g_n=2^{2^n}+1$ and $g_n=g_0\cdot g_1 \cdots g_{n-1}+2$. The gcd must divide 2, but it cannot be 2 as $g_n$ cannot be divided by 2. Hence $\gcd(g_a,g_b)=1$

-1

The fallacy your professor is referring to is that you wrote down a statement that is false (even in its context). The induction step is always to prove something of the form: For any natural number $n$, if $P(n)$ is true, then $P(n+1)$ is true. where $P$ is the property that you want to prove about every natural number. You start by proving that $0$ ...

0

Assume that $$P(n) \text{ is true}\implies \sum_{i=1}^n i(i+1)=\frac {n(n+1)(n+2)}3$$ First we check for the base step: $1*(1+1)=2=\frac {1*(1+1)*(1+2)}3$ Hence $P(1)$ is true. Now assume that $P(k)$ is true for some $k \in N$. So $$\sum_{i=1}^ki(i+1)=\frac {k(k+1)(k+2)}3$$ Now we check for the truth of $P(k+1)$. ...

1

It seems like you do not really understand why induction is a valid proof technique (it may also help to read this post on how to write a clear induction proof). The "fallacy" you seem to have in mind does not make a great deal of sense; the goal of induction proofs (assuming you're trying to prove a statement $S(n)$ is true) is, indeed, to move from the ...

3

The key in this problem is really an algebraic "trick" or manipulation to coax out the right-hand side from the left. You've presumably verified the base case (for $n=2$). You then assumed that $\color{blue}{\sum_{i=1}^k\frac{1}{i^2}=2-\frac{1}{k}}$ for some fixed $k\geq 2$. Now, your goal is to use this assumption (called the inductive hypothesis) to prove ...

2

Lets say the statement is true for $n=k$ i.e., $(1+x)^k-xk-1$ is divisible by $x^2$ (Lets say, $(1+x)^k-xk-1=mx^2$ ) To show $(1+x)^{k+1}-x(k+1)-1$ is divisble by $x^2$ $(1+x)^{k+1}-x(k+1)-1$ $=(1+x)^k(1+x)-xk-x-1$ $=(1+x)^k+x(1+x)^k-xk-x-1$ $=\{(1+x)^k-xk-1\}+x(1+x)^k-x$ $=mx^2+x \{(1+x)^k-1\}$ = $=mx^2+x \{(1+x)^k-1-xk+xk\}$ $=mx^2+x ... 1 The base case is trivial. Suppose the result holds for$k$; then $$(x+1)^k-kx-1=x^2f_k(x)$$ for some polynomial$f_k$. Therefore$(x+1)^k=1+kx+x^2f_k(x)and \begin{align} (x+1)^{k+1}-(k+1)x-1 &=(x+1)(x+1)^k-kx-x-1\\[6px] &=(x+1)(1+kx+x^2f_k(x))-kx-x-1\\[6px] &=\color{red}{x}+kx^2+x^3f_k(x)+\color{red}{1}+\color{red}{kx}+ ... 4 By the Binomial theorem,(x+1)^n$ends in$nx+1$, so that the remaining terms are multiples of$x^2$. By induction,$(x+1)^n$ends in$nx+1$. This is true for$n=1$,$(x+1)^1$ends in$x+1$. Now assume that$(x+1)^n$ends in$nx+1$. Multiplying by$x+1$, we get$nx+x+1$and higher order terms, hence$(x+1)^{n+1}$ends in$(n+1)x+1$. 2 Hint: $$(x+1)^{n+1}-(n+1)x-1=(x+1)(x+1)^n-nx-x-1$$$$=(x+1)((x+1)^n-nx-1)+(nx+1)(x+1)-nx-x-1$$$$=(x+1)((x+1)^n-nx-1)+nx^2$$ 2 Do you have to use induction? Let's say that the flake after$j$steps has$n_j$sides of length$s_j$, now since you replace each side with four of length$s_j/3$and thereby adding a equilateral triangle of side$s_j$you will end up with$s_{j+1}$=$s_j/3$and$n_{j+1} = 4n_j$and the area added in this step to be$n_j a_0 s_j^2/9$. Now it's easy to ... 2 By the induction hypothesis, $$3^k+7^k-2=8m$$ for some integer$m$. Then$3^k=8m+2-7^kand so \begin{align} 3^{k+1}+7^{k+1}-2 &=3\cdot 3^k+7^{k+1}-2\\ &=3(8m+2-7^k)+7\cdot7^{k}-2\\ &=24m+6-3\cdot7^k+7\cdot7^{k}-2\\ &=4(6m+1+7^k) \end{align} Can you finish up? 4 You can find a proof here. But my favorite proof takes a different course. Let\mathbf x = \{x_n\}_{n \in \Bbb N}$and$\mathbf y = \{y_n\}_{n \in \Bbb N}$be sequences satisfying the Fibonicci recurrence relation. That is: for$n > 1, x_n = x_{n-1} + x_{n-2}$and$y_n = y_{n-1} + y_{n-2}$. Note that for any real number$a$,$a\mathbf x = \{ax_n\}_{n ...

0

Initial step: $X_2$ = $X_1$ = 1. Does $x_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right )^1 - \left (\frac{1-\sqrt{5}}{2}\right )^1\right ]$ = 1 = $X_2$ = $X_1$ ? Induction step: Assume the result is true for $X_{n-1}$ and $X_n$. Then $X_{n+1} = X_n + X_{n - 1} =\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right )^n - \left ... 0 With induction, you are given the formula. So you simply have to show it holds for the base case(s), and then use the formula for n and n+1 to show it holds for n+2. You might want to review induction for easier problems. Don't feel like you have to come up with that formula for$X_n$out of nowhere, which is harder than just showing it works. 0$(3^{k+1}+7^{k+1}-2)=3^k+7^k-2+2\cdot3^k+6\cdot7^k$So, it is enough to show that$8$divides$2\cdot3^k+6\cdot7^k=6\cdot3^{k-1}+6\cdot7^k$Also,$3^{odd}=3$mod$(8)$,$3^{even}=-1$mod$(8)7^{odd}=-1$mod$(8)$,$7^{even}=1$mod$(8)$. implies$6\cdot3^{k-1}+6\cdot7^k=0$mod$(8). 5 Notice \begin{align} 3^k\cdot 3+7^k\cdot 7-2&=3^k\cdot(3+4)-3^k\cdot 4+7^k\cdot 7-2\cdot 7 +2\cdot 7-2\\ &=7(3^k+7^k-2)-3^k\cdot 4+2\cdot 7-2\\ &=7(3^k+7^k-2)-3^k\cdot 4+12\\ &=7(3^k+7^k-2)-12\cdot(3^{k-1}-1)\\ \end{align} by hypothesis8$divides$3^k+7^k-2$, and for$k\ge 1$the number$3^{k-1}-1$is even, then$8$divides ... 3 We have$3^{k+2}=9\cdot 3^k=3^k+8\cdot 3^k$and$7^{k+2}=7^k+(8)(6)7^k$. Make separate arguments for$c$odd and$c$even, using base cases$c=1$and$c=2$respectively. Or else (essentially the same idea) use strong induction. 0 For 1bii, $$\sum_{i=1}^n p(i) =\sum_{i=1}^n (q(i)-q(i-1)) =(q(1)-q(0))+(q(2)-q(1))+...+(q(n)-q(n-1))$$ and note that everything cancels out except$q(n)-q(0)$. Note: I do not think that the problem should have assumed that$q(0) = 0$. 0 The base case, for$n=1$, is$g_0 = g_1-2$or$2^1+1 = 2^2+1-2$or$3 = 5-2\$. From this, you can use induction.

2

It amounts to check that $$-\frac1n+\frac1{(n+1)^2}<-\frac1{n+ 1}\iff\frac1{(n+1)^2}<\frac1n-\frac1{n+ 1}=\frac1{n(n+1)}—\iff n+1>n.$$

Top 50 recent answers are included