# Tag Info

## New answers tagged induction

0

The simplest to state and prove version of "real induction" on $\mathbb{R}^n$ is the following: suppose $A\subseteq\mathbb{R}^n$ is a nonempty closed subset such that if $p\in A$, then some ball around $p$ is contained in $A$. Then $A$ is all of $\mathbb{R}^n$. (Proof: The hypotheses just say $A$ is a nonempty clopen subset of $\mathbb{R}^n$, and ...

1

The answer is, of course, yes. Lets consider the case with "classical" induction. The argument basically goes like this: Let $P(n)$ be statements indexed by $n\in\mathbb{N}$. Suppose $P(1)$ is true, and $P(i)\Longrightarrow P(i+1)$, then $P(n)$ is true for all $n\in\mathbb{N}$. Fundamentally, this is just saying that if you have a situation where The ...

2

We can systematically decompose the problem top-down. Let $f(n)$ be the direction in which the $n$-th person (with indices wrapping round the ring) does his disgusting thing, $-1,0,1$ for left, centre and right respectively. Note that the number of ways is equivalent to the number of possible $f$ that satisfies the corresponding conditions, as long as $n \ge ... 10 For$n$people in a row, not a circle, the number is$Fib(n+1)$. For example for four people there are five possibilities. For$n$people ($n \gt 2$) in a circle: one possibility is that they all shift left; another is that they all shift right the person in seat 1 may use their own chair leaving a row of$n-1$people the person in seat 1 may use the ... 1 There are two 'kinds' of ways for this happening (for$n>2$): 1) All of them are doing the same thing: under his own chair ($1$), to the right ($1$) or to the left ($1$). So there are$3$ways in this kind. 2) There are some 'pairs' of people and in each pair they place their gum under each other's chair. These sum up as ... 1 This answer addresses this part (really the main part) of your question: I need this in order to complete my proof that$1 + \frac{n}{2} \leq H_{2^n}$, but don't have any ideas. Consider the following exercise, the solution of which answers your question directly (skip ahead to the "induction proof" part of this answer for a proof of your claim without ... 3 Here's an alternate proof, with generating functions instead of induction. Note that $$\sum_{i=1}^n \frac{i}{(i+1)!}$$ is the sum of the first$nterms of the series \begin{align*} \sum_{i=1}^\infty \frac{i x^i}{(i+1)!} &= x \sum_{i=1}^\infty \frac{i x^{i-1}}{(i+1)!} \\ &= x \frac{d}{dx} \sum_{i=1}^\infty \frac{x^i}{(i+1)!} \\ &= x ... 1 $$\frac{1}{2!}+\frac{2}{3!}+...+\frac{n}{(n+1)!}=\frac{(n+1)!-1}{(n+1)!}$$ Name asp(n)1 step:$$n=1 \to p(1):\frac{1}{2!}=\frac{2!-1}{2!}$$ 2nd step :assume $$n=k \to p(k):\frac{1}{2!}+\frac{2}{3!}+...+\frac{k}{(k+1)!}=\frac{(k+1)!-1}{(k+1)!}$$ 3rd step :prove for n=k+1 n=k+1 \to ... 2 Here is the key part of the induction argument (moving from the left-hand side of n=k+1 to the right-hand side): \begin{align} \sum_{i=1}^{k+1}\frac{i}{(i+1)!} &= \sum_{i=1}^k\frac{i}{(i+1)!}+\frac{k+1}{(k+2)!}\tag{by defn. of \Sigma}\\[1em] &= \frac{(k+1)!-1}{(k+1)!}+\frac{k+1}{(k+2)!}\tag{by ind. hyp.}\\[1em] &= ... 4 It is not the correct formula. It should be:\frac{1}{2!}+\frac{2}{3!}+...+\frac{n}{(n+1)!}=\frac{(n+1)!-1}{(n+1)!}$$Now the base case works. For the inductive step you need to prove:$$\frac{1}{2!}+\frac{2}{3!}+...+\frac{k+1}{(k+2)!}=\frac{(k+2)!-1}{(k+2)!} \qquad \mathrm{given}$$... 2 First, see that this sum has 2^n terms. Then, \forall k\in \{1,\dots,2^n\}, you have \frac{1}{2^n+k}\geq\frac{1}{2^{n+1}}. Summing these inequalities, you get the result. 2$$\sum_{k=1}^{2^n} \frac{1}{2^n+k} \geq \sum_{k=1}^{2^n} \frac{1}{2^n+2^n} =\sum_{k=1}^{2^n} \frac{1}{2^{n+1}}$$the rightmost sum equals \frac{1}{2}, in fact we have a strict inequality. 3 Hint: how many summands are there? What is the smallest summand? 2 Hint for every 1\leq k\leq 2^n$$\frac{1}{2^n+k}\geq \frac{1}{2^{n+1}} $$do every term in your sum is greater then \frac{1}{2^{n+1}} and in the sum there is 2^n terms so your sum is greater then 2^n times \frac{1}{2^{n+1}} \cdots 0 Suppose we knew for 2 values of n F_n \ge 2^{\frac n2} i.e for n = 6 and n = 7. We know this holds for n=6 and n=7. We also know that F_{n+1} = F_{n} + F_{n-1} So we assume for some k and k-1 (7 and 6) F_{k-1} \ge 2^{\frac {k-1}{2}} and F_{k+1} \ge 2^{\frac {k+1}{2}} We know F_{k} \ge F_{n-1} so F_{k+1} \ge 2 \cdot F_{n-1} Using the ... 5 We have that F_n>F_{n-1} then$$F_{n+1}=F_n+F_{n-1}>2F_{n-1}>2\cdot2^{(n-1)/2}=2^{(n+1)/2}$$0 Your problem has already been answered in details. I would like to point out that if you want to train your inductive skills, once you have a solution to your problem, you still can explore it from many other sides, especially using visual proofs that can be quite effective. And find other proofs. Some are illustrated in An Invitation to Proofs Without ... 0 Suppose \sum_{i=1}^k 2^i = 2^{k+1} - 2 for all k < n. Then, choose some k with 1 < k < n. \begin{array}\\ \sum_{i=1}^n 2^i &=\sum_{i=1}^k 2^i +\sum_{i=k+1}^n 2^i\\ &=2^{k+1} - 2 +2^k\sum_{i=k+1}^n 2^{i-k}\\ &=2^{k+1} - 2 +2^k\sum_{i=1}^{n-k} 2^{i}\\ &=2^{k+1} - 2 +2^k(2^{n-k+1}-2)\\ &=2^{k+1} - 2 +2^{n+1}-2^{k+1}\\ ... 0 We have to prove,$$\sum_{i=1}^{n}2^{i}=2^{n+1}-2$$Step 1: Setting n=1 in the above equality, we get$$\sum_{i=1}^{1}2^{i}=2^{1+1}-2\iff 2=4-2\iff 2=2$$hence it holds for n=1 Step 2: Assuming that it holds for n=k, we get$$\sum_{i=1}^{k}2^{i}=2^{k+1}-2$$Step 3: Now, setting n=k+1 in the given equality, we get ... 2 For strong induction, a proof goes something like this: Proof of a base case: here n= 1 will do: 2 = 4 - 2. The only thing different between "strong" and "regular" induction is how we state the inductive step: We assume that for ALL n_0 \leq k < n, the theorem holds, and then use that to show it holds for k = n. This means we have access to ... 1 Your calculation$$\sum_{i=1}^{k+1}2^i=\sum_{i=1}^{k}2^i+2^{(k+1)+1}-2$$is false. What's true is that$$\sum_{i=1}^{k+1}2^i=\sum_{i=1}^k2^i+2^{k+1},$$and 2^{k+1}\neq 2^{(k+1)+1}-2 in general. You can apply the induction hypothesis to the first term on the right to get what you want, although this is normal induction, rather than strong induction. 0 Induction n-1\to n makes it more compact.$$\left(\sum_1^{n-1}i+n\right)^2=\left(\sum_1^{n-1}i\right)^2+2n\sum_1^{n-1}i+n^2=\left(\sum_1^{n-1}i\right)^3+n^2(n-1)+n^2=\left(\sum_1^{n-1}i\right)^3+n^3.0 We could also start the induction step from the RHS. This way we need only to cope with a square of a binom and not with a cube of a binom. Induction step n \rightarrow n+1: \begin{align*} \left(\sum_{i=1}^{n+1}i\right)^2&=\left(\sum_{i=1}^{n}i+(n+1)\right)^2\\ &=\left(\sum_{i=1}^{n}i\right)^2 + 2(n+1)\sum_{i=1}^{n}i+(n+1)^2\\ ... 2 You could use induction but maybe we can appeal to a counting argument: Write P= (x+1)(x+1)(x+1)\cdots (x+1) where there are m instances of x+1. Now, when we expand this, if we respect the order of the multiplication, then an arbitrary term will be a product of 1's and x's that satisfies: the number of instances of 1+ the number of ... 3 We will adapt a non-inductive, combinatorial proof of the binomial theorem. We seek the expansion of \begin{align*} (x+1)^m &= (x+1)\cdots(x+1) \\ &= a_m x^m + a_{m-1} x^{m-1} + \cdots + a_1 x + a_0 \end{align*} Each integer coefficient can be treated as the number of times the variable of the term appears in a full expansion. Note that each term in ... 2 Proceed by induction on m. For m = 0, the statement holds; now assume true for all values \leq m. Then for m + 1, we have \begin{align} (x+1)^{m+1} &= (x + 1) (x + 1)^m \\ &= (x + 1)\sum\limits_{k = 0}^m \binom{m}{k}x^k &\text{ by the inductive hypothesis} \\ &=\sum\limits_{k = 0}^m \binom{m}{k}x^{k + 1} + \sum\limits_{k = 0}^m ... 1 You may prove by induction that \delta(\mathcal{G}_1),\dots,\delta(\mathcal{G}_k),\mathcal{G}_{k+1},\dots,\mathcal{G}_n are independent (for all k\le n)... For k=0 this is the assumption (\mathcal{G}_{1},\dots,\mathcal{G}_n are independent). For k>1 assume that ... 2 Step 1: putting n=1, we getx^{2n}-y^{2n}=x^2-y^2=(x-y)(x+y)$$above number is divisible by (x+y). Hence the statement is true n=1 step 2: assuming that for n=m, (x^{2n}-y^{2n}) is divisible by (x+y) then we have$$(x^{2m}-y^{2m})=k(x+y) \tag 1$$Where, k is an integer step 3: putting n=m+1 we get$$x^{2(m+1)}-y^{2(m+1)}$$... 3$$x^{2(k+1)}-y^{2(k+1)}=x^2x^{2k}-y^2y^{2k}=x^2x^{2k}\color{green}{-x^2y^{2k}+x^2y^{2k}}-y^2y^{2k}\\ =x^2(x^{2k}-y^{2k})+(x^2-y^2)y^{2k}.$$The first term is divisible by x+y by the induction hypothesis, and the second as well, by direct factorization. 0 For n=k, assume P(k) is true, we have$$x^{2k}-y^{2k}=A(x-y), where A is a polynomial. For n=k+1, \begin{align} x^{2k+2}-y^{k+2}&=x^2[A(x-y)+y^{2k}]-y^{2k+2}\\&=A(x-y)x^2+x^2y^{2k}-y^{2k+2}\\&=A(x-y)x^2+y^{2k}(x^2-y^2)\\&=A(x-y)x^2+y^{2k}(x-y)(x+y)\\&=(x-y)[Ax^2+y^{2k}(x+y)]\\&=B(x-y)\text{, where } B \text{ is a ... 8 Hint: Rewrite:x^{2k+2}-y^{2k+2}=(x^{2k+2}-y^{2k}x^2)+(y^{2k}x^2-y^{2k+2})=x^2(x^{2k}-y^{2k})+y^{2k}(x^2-y^2).$$Added: Note it can be proved without induction:$$x^{2n}-y^{2n}=(x^2)^n-(y^2)^n=(x^2-y^2)(x^{2(n-1)}+x^{2(n-2)}y^2+\dots+x^2y^{2(n-2)}+y^{2(n-1)}),$$and the first factor is divisible by x+y. 1 Brief answer: In principle we use strong induction, showing that if f_k=\frac{2}{3}\cdot 2^k +\frac{1}{3}\cdot(-1)^k for any k\lt n, then f_n=\frac{2}{3}\cdot 2^n+\frac{1}{3}\cdot (-1)^n. Note that f_n=f_{n-1}+2f_{n-2}. It follows by the induction assumption that$$f_n=\frac{2}{3}\cdot 2^{n-1}+\frac{4}{3}\cdot ... 0 You have \begin{align} \sum_{k=1}^{n} k &= 1 + 2 + 3 + \cdots + n \\ &= n + (n - 1) + (n - 2) + \cdots + 1 \\ \end{align} where in the second line we just reversed the order in which we summed. Now if we add the two lines, notice that term by term we getn + 1, i.e \begin{align} (n) + 1 &= n + 1 \\ (n - 1) + 2 &= n + 1 \\ (n - 2) + 3 ... 1 Here is an exercise in using induction, for you. Prove that, for a positive integern$and a (positive) prime number$p,$the exponent$E$of$p$in the prime factorization of$n!$is Legendre's value, $$E = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \left\lfloor ... 3 I don't see any reason why it isn't possible. It is possible--it's just simply less frequently encountered. There have been a number of posts (e.g., induction on real numbers) that deal with induction as not related to natural numbers. There have also been quite a few articles, some open source and some professionally published (not mutually exclusive), ... 9 It is possible indeed, the principle of induction is much more general than you may think. There are many induction theorems you can prove for the most intuitive of them if you understand the principal idea which is well-foundedness, or well-orderedness. (but maybe it is too soon for you to benefit from the effort you would have to make to understand these ... 1 I solved this problem for someother OP. Here you go! 0 Ramsey's theorem For any given number of colors c, and any given integers n1, . . . ,nc, there is a number, R(n1, ..., nc), such that if the edges of a complete graph of order R(n1, . . . , nc) are colored with c different colors, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all color i. The two ... 0 It comes to the same as proving that: 1) \sum_{k=1}^{1}k^{3}=\left(\sum_{k=1}^{1}k\right)^{2} (trivial) and: 2) \left(\sum_{k=1}^{n}k\right)^{2}-\left(\sum_{k=1}^{n-1}k\right)^{2}=n^{3} for n=2,3\dots Note that the LHS equals: ... 1 We have$$\sum_{k=1}^{n} k^3 = \bigg( \sum_{k=1}^{n}k\bigg)^2$$1. Putting n=1 in the above equality, we get$$\sum_{k=1}^{1} k^3 = \bigg( \sum_{k=1}^{1}k\bigg)^2 (1)^3=(1)^2\iff 1=1$$Hence, the equality holds for n=1 Assuming that it holds for n=p then we have$$\sum_{k=1}^{p} k^3 = \bigg( \sum_{k=1}^{p}k\bigg)^2$$... 1 A hint is to write$$\left(p + \sum_{k=1}^{p-1}k\right)^2$$and then apply binomial theorem when treating the sum as an already known number (it is an arithmetic sum). 3 We have$$\Big(\sum_{k=1}^{p+1} k\Big)^2=\Big(\sum_{k=1}^p k + (p+1)\Big)^2 = \Big(\sum_{k=1}^p k\Big)^2 + \color{blue}{2 (p+1)\Big(\sum_{k=1}^p k\Big)+(p+1)^2}.$$Since \sum_{k=1}^p k = \frac12 p(p+1),$$\color{blue}{2(p+1)\Big(\sum_{k=1}^p k\Big)+(p+1)^2} = p(p+1)^2+(p+1)^2=(p+1)^3.$$1 Since several answers have already proven the result via induction, I see no harm in recording an additional proof that does not use induction. We claim for all n\ge 1,$$\int_{0}^{1} (x\log(x))^n \, dx = \frac{(-1)^n n!}{(n+1)^{n+1}}$$This can be shown using differentiation under the integral sign; set k=n below:$$f(n) = \int_{0}^{1} x^n \, dx = ... 1 Hint So$L_n = \phi^n + \Phi^n$and$L_{n-1} = \phi^{n-1} + \Phi^{n-1}$, and we have $$L_{n+1} = L_n + L_{n-1} = \phi^n + \Phi^n + \phi^{n-1} + \Phi^{n-1} = \phi^{n-1} (\phi+1) + \Phi^{n-1} (\Phi+1)$$ and now use the fact that$\phi$and$\Phi$solve$x^2 = x+1$, so$\phi+1=\phi^2$and$\Phi+1 = \Phi^2$. Can you finish the proof? 0 If$n\ge4$, then$n! = n\cdot (n-1) \cdots 5 \cdot 4! \ge 2 \cdot 2 \cdots 2\cdot 2^4 = 2^{n-4} \, 2^4 = 2^n$. This argument actually proves that$n! \ge 4^{n-4}\, 2^4 = 4^{n-2}$, for$n\ge 4$, which is better but not as nice. (Induction is hidden, as always, in the dots. Here, it is in$x_1, \dots, x_m \ge a \implies x_1 \cdots x_m \ge a^m$.) 0 In general, induction works like this. Let a statement$\mathcal{S}$depend on a natural number$n \in \mathbb{N}$. We write the statement as$\mathcal{S}_n$. Induction means to proof the following two conditions: $$\mathcal{S}_0 = \textrm{true} \tag{1}\\$$ $$\mathcal{S}_n = \textrm{true} \Longrightarrow \mathcal{S}_{n+1} = \textrm{true}\tag{2}$$ ... 3 As KyleW points it, this should hopefully not go off as an unanswered question, particularly if you feel like you have figured it out / solved it. Thus, consider my proof below to complement or complete your own. Claim: For$n\geq 4$, denote the statement involving$n$by $$S(n) : 2^n <n!.$$ Base step ($n=4$):$S(4)$says that$2^4=16<24=4!$, and ... 1 I'll try to sketch out a proof similar to the one you provided, and then I will flesh out why this approach does not work (as an aside, you may find this thread on fake induction proofs to be of use in picking up on faulty reasoning sometimes used in induction proofs). Claim: For every non-negative integer$n, 10n=0$. Base case:$10\cdot 0=0$. ... 3 You cannot go like this from$k=0$to$k=1$(i.e.$k=1$cannot be expressed in the form$m+l$as you wrote). 3 I believe that you are either misinterpreting the video, the video is wrong, or something else is going on because, if$\sum_{i = 0}^{n} \binom{n + i}{i} = \binom{2n + 1}{n + 1}$and$\sum_{i = 0}^{n} \binom{n + i}{i} = \binom{n + k + 1}{k}$for$0 \leq k \leq n$, that would imply$\sum_{i = 0}^{n} \binom{n + i}{i} = \binom{2n + 1}{n + 1} = \binom{n + k ...

Top 50 recent answers are included