# Tag Info

0

It seems like you're not quite understanding what induction is. And that's completely understandable - it took me a while to get it. For most people, it doesn't make sense - how would assuming something that you don't know is true ever prove something? The domino analogy is nice, but not very helpful unless you already understand induction. I always think ...

2

The induction scheme can be proved and generalized to be used on sets bigger than the natural numbers (The proof can be done under ZFC, which is an acceptable axiomatic system which is strong enough to describe most mathematics we know). Lets prove for example, the induction principle for well ordered sets. Suppose you have a well ordered set (every subset ...

-1

No, there is no proof of induction. Induction is considered to be a mathematical axiom. An axiom is a rule in mathematics that does not require a proof (since it is thought to be the starting point or premise of any mathematical proof). This is an excerpt from Wikipedia's article on axioms. In both senses, an axiom is any mathematical statement that ...

12

Suppose we want to show that all natural numbers have some property $P.$ One route forward, as you note, is to appeal to the principle of arithmetical induction. The principle is this: Suppose we can show that (i) $0$ has some property $P$, and also that (ii) if any given number has the property $P$ then so does the next; then we can infer that (iii) all ...

-2

Read the statement of induction carefully. Its first proves the base case, which obviously doesn't need a proof. Then we assume that the given expression is true for $k$. Now we use our logic to deduce that if it is true for $k$, then it has to be true for every other number given by the condition. It is an axiom, we take it to be true. For example we ...

1

It is certainly possible to use induction more than once in a proof. Perhaps one of the more interesting applications of this idea is Cauchy induction. To perform Cauchy induction, one first proves a base case, $P(1)$, and then proves $P(n)$ implies $P(2n)$. This inductively implies $P(2^n)$. Finally, you use decreasing induction, $P(n)$ implies $P(n-1)$, ...

1

$\underline{\text{Proof by induction:}}$ First, show that this is true for $n=0$: $5^0-1=0$ Second, assume that this is true for $n$: $5^n-1=4k$ Third, prove that this is true for $n+1$: $5^{n+1}-1=$ $5\cdot5^n-1=$ $5\cdot5^n-5+4=$ $5\cdot(\color{red}{5^n-1})+4=$ $5\cdot\color{red}{4k}+4=$ $20k+4=$ $4\cdot(5k+1)$ Please note that the assumption ...

1

Here is my solution: Let $5^n-1$ be divisible by 4. It means that $5^n-1=4k$ for some integer $k$, our base step is at $n=0$ and is clearly true. We must prove if $5^n-1=4k$ then $5^{n+1}-1=4j$. $5(5^n-1)=4(5k)$ whcih is equivalent to $5^{n+1}-1=4(5k+1)$, therefore $j=5k+1$. Q.E.D

0

Assume that $5^k-1$ is divisible by $4$, then we have that $$(5^k-1)+(4\times 5^k)=5^k+4\times 5^k-1=5\times 5^k-1=5^{k+1}-1$$ is also divisible by $4$.

7

The Principle of Mathematical Induction says that for all "properties" $P$, $$\left(P(0)\land\forall k\in \mathbb N\left(P(k) \implies P(k+1)\right)\right)\implies \forall n\in \mathbb N(P(n)).$$ So you're basically asking how to write the $\forall k\in \mathbb N\left(P(k)\implies P(k+1)\right)$ bit. It's a universal statement. It's common to start those ...

0

To prove definition 2 from definition 1 let $S = \{n \ | \ P(n)\}$ and to prove definition 1 from definition 2 let $P(n)$ be the statement "$n \in S$".

2

We are given that n!= \left\{\begin{align}1\quad \text{for}\quad n=0\\n\cdot(n-1)!\quad \text{for}\quad n>0\end{align}\right. and wish to show that $$n! = \prod_{i=1}^ni$$ We start with $n=1 \implies 1! = 1\cdot(0!) = 1 = \prod_{i=1}^1 i$ Now, let's assume $(n-1)! = \prod_{i=1}^{n-1} i$, then $$n! = n\cdot(n-1)! = n\prod_{i=1}^{n-1} i = ... 0 Induction step: If$$(n-1)!=(n-1).(n-2)\dots3.2.1$$then by definition$$n!=n.(n-1)!=n.(n-1).(n-2)\dots3.2.1$$0 The author is leaving out (arguably tedious) steps. This may be because the author thinks they are obvious, and so not worth mentioning. This may be because the author thinks they are not too far from obvious, and so leaves the additional steps as an understanding-enhancement exercise for the reader. Note that k is positive and a^2\ge0. (Do you see why ... 1 Your property 1 is effectively the Recursion Theorem. It is often (sloppily) referred to as an "inductive procedure," which is to some extent reasonable, because we need the Principle of Mathematical Induction (or, equivalently, the well-ordering property of the natural numbers) to prove it. The rough idea is that if we can start a procedure, and explicitly ... 2 First recall the famous limit formula for the constant e:$$\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n=e\approx 2.7182 \ldots<3.\tag{1}$$Now recall the binomial theorem: Binomial theorem:$$(x+y)^n=\sum_{i=0}^n\binom{n}{i}x^{i}y^{n-i}.\tag{2}$$We may use (2) (with x=1/k, y=1, and n=k+1) to rewrite ... 0 We will use induction to show that \;\;\color{red}{3^n n!>n^n} for all \color{blue}{n\ge1}: 1) This is true for n=1, since 3>1. 2) Let n\in\mathbb{N} with 3^n n!>n^n. Then 3^{n+1}(n+1)!=3(n+1)\big(3^n n!\big)>3(n+1)\big(n^n\big), \;\;\;and 3(n+1)(n^n)>(n+1)^{n+1}\iff3n^n>(n+1)^{n}\iff3>\big(1+\frac{1}{n}\big)^n,\; ... 0 we have to show that$$(n+1)!>\frac{(n+1)^{n+1}}{3^{n+1}}$$multiplying$$n!>\frac{n^n}{3^n}$$by$$n+1$$we get$$(n+1)!>\frac{n^n(n+1)}{3^n}$$this must be greater as$$\frac{(n+1)^{n+1}}{3^{n+1}}$$this is true since$$\left(1+\frac{1}{n}\right)^n<3$$1 HINT: If m!>\dfrac{m^m}{3^m} \implies(m+1)!>m\cdot\dfrac{m^m}{3^m} It is sufficient to show m\cdot\dfrac{m^m}{3^m}>\dfrac{(m+1)^{m+1}}{3^{m+1}} \iff3>\left(1+\dfrac1m\right)^{m+1} Now \left(1+\dfrac1m\right)^{m+1}>\left(1+\dfrac1{m+1}\right)^{m+1} Now see How is a_n=(1+1/n)^n monotonically increasing and bounded by 3? and ... 1 Well, the number of ways to write m as a+b are clearly m+1, ranging from 0+(m) to (m)+0. So the number of ways to write n as a+b+c are given by:$$ \sum_{c=0}^{n}(n-c+1)=\sum_{d=0}^{n}(d+1)=\sum_{k=1}^{n+1}k $$by setting d=n-c and k=d+1. 0 Here is an apparently non-standard proof, involving no gradients or Hessians: http://www.cs.bgu.ac.il/~mlt142/CsWiki/Blogs/Post_Karyeh_55db5950bd339?format=standalone 5 "And so we continue, this procedure must stop because we know that n is in the set A." That's induction right there; you are writing it informally enough that the induction is not explicit. 0 Notice, we have to prove$$\binom{2n}{n}=\frac{1\cdot 3\cdot 5\cdots (2n-1)}{n!}2^n$$Step 1: Setting n=1, we get$$\binom{2}{1}=\frac{1}{1!}2^12=2$$Hence, it holds for n=1 Step 2: Assuming it hold for n=k then setting n=k, we have$$\binom{2k}{k}=\frac{1\cdot 3\cdot 5\cdots (2k-1)}{k!}2^k\frac{(2k)!}{(k!)^2}=\frac{1\cdot 3\cdot ...

0

If $n=1$ then $(2n)!/2^{n}n! = 1$. Let $n \geq 1$. If $(2n)!/2^{n}n! = k$ for some $k \in \mathbb{N}$, then $$\frac{(2n+2)!}{2^{n+1}(n+1)!} = \frac{(2n+2)(2n+1)(2n)!}{(2n+2)2^{n}n!} = (2n+1)k \in \mathbb{N},$$ qed.

4

\begin{align} \frac{(2n)!}{2^n n!} = \frac{(2n) \times (2n - 1) \times \cdots \times 1}{(2n) \times (2n - 2) \times \cdots \times 2} = (2n - 1) \times (2n - 3) \times \cdots \times 1 \in \mathbb{Z}. \end{align}

1

W/O induction, for $n>0,$ $$\dfrac n{n+1}>\dfrac12\iff 2n>n+1\iff n>1$$

1

For $n=1$ we have $n/(n+1) = 1/2$. Let $n \geq 1$. If $n/(n+1) \geq 1/2$, i.e. if $2n \geq n+1$, then $2(n+1) = 2n+2 \geq n+1+2 = n+3 > n+2$, i.e. $(n+1)/(n+2) > 1/2$, qed.

1

I have a shorter proof: by the AM-GM inequality, $$\forall t>0,\qquad \frac{1}{1+t}\geq \frac{1}{\left(1+\frac{t}{2}\right)^2}\tag{1}$$ as well as: $$\forall t>0,\qquad \frac{1}{1+t}\leq \frac{1+(1+t)^2}{2(1+t)^2}.\tag{2}$$ Now it is enough to integrate both sides of $(1)$ and $(2)$ over $(0,x)$ to prove the statement.

0

I think the question is looking too complicated only because of too much symbolism. Let $r = K - L > 0$. Thus we the chain of integers $$L < L + 1 < L + 2 < \dots < L + r - 1 < L + r = K$$ and hence a chain or rationals $$\frac{L}{n} < \frac{L + 1}{n} < \dots < \frac{L + r - 1}{n} < \frac{L + r}{n} = \frac{K}{n}$$ and clearly ...

0

When $n=1$, $LHS=4=RHS.$ Assume, when $n=k$, $LHS=RHS$. When $n=k+1$, $LHS=(k+2)^2+(k+3)^2+\dots+(2k+1)^2 + (2(k+1))^2 \\=k(2k+1)(7k+1)/6-(k+1)^2+(2k+1)^2+(2(k+1))^2 \\=[k(2k+1)(7k+1)+18(k+1)^2+6(2k+1)^2]/6 \\=[(2k+1)(7k^2+13k+6)+18(k+1)^2]/6 \\=[(2k+1)(7k+6)(k+1)+18(k+1)^2]/6 \\=(k+1)(14k^2+37k+24)/6 \\=(k+1)(2(k+1)+1)(7(k+1)+1)/6=RHS.$

1

Let $f(x) = \frac{2x}{x+2}$, $g(x) = \ln(1+x)$, $h(x) = \frac{x^2 + 2x}{2x+2}$. $f(0) = 0$, $g(0) = 0$, $h(0) = 0$. $f' = \frac{2(x+2)-2x}{(x+2)^2} = \frac{4}{(x+2)^2}$, $g' = \frac{1}{1+x}$, $h'= \frac{(2x+2)(2x+2)-2(x^2+2x)}{(2x+2)^2}=\frac{2x^2+4x+4}{(2x+2)^2}$ Now it is easy to check that $$f'=\frac{4}{(x+2)^2} \leq g' = \frac{1}{1+x} \leq ... 0 There are a few caveats: We cannot assume that L (or K) is \ge0, we only know that they are integers. Therefore I would suggest that you try to show that (under the assumption that the claim is false)$$\tag {$1_k$} \frac{L+k}n\text{ is not an upper bound}$$holds for all k\in\mathbb N_0. We are already given that (1_0) holds. Assume (1_k) holds. ... 3 Hint : Consider$$f(x)=\ln (1+x)-\frac{2x}{2+x}$$and$$g(x)=\frac{x(x+2)}{2(x+1)}-\ln(1+x)$$Show f and g are monotone increasing functions.. 1 We have to prove$$(n+1)^2+(n+2)^2+(n+3)^2+\ldots+(2n)^2=\frac{n(2n+1)(7n+1)}{6}$$\color{red}{\text{Step}\ 1}: Setting n=1 in the above identity, we get$$(1+1)^2=\frac{1(2\cdot 1+1)(7\cdot 1+1)}{6}4=\frac{3\times 8}{6}4=4$$\color{red}{\text{Step} \ 2}: Assuming the identity holds for n=k then we get ... 6 Let s(n)=1^2+2^2+...+n^2=\sum_{j=1}^nj^2.. You want calculate s(2n)-s(n). We know that s(n)=\frac{n(n+1)(2n+1)}{6}, then s(2n)=\frac{2n(2n+1)(4n+1)}{6}. It follows that$$s(2n)-s(n)=\frac{2n+1}{6}(8n^2+2n-n^2-n)=\frac{2n+1}{6}(7n^2+n)=\frac{n(2n+1)(7n+1)}{6}.$$1 The general theorem of mathematical induction goes like this: Suppose that "\Phi" is a proposition involving the variable "n". Actually let's call the proposition \Phi(n), and agree that whenever we write "\Phi(\text{something})" the reader is meant to substitute the "something" in for n. If \Phi(0) holds, and if \Phi(n+1) holds whenever ... 2 You are making the assumption that f(n) = \text{ sum of the first } n \text{ integers} during your induction. When you evaluate f(1) you make this assumption in how you evaluate. And in your induction step you mean to assert:$$f(n+1) = f(n) + (n+1)$$before going on with your proof. Implicit in this assumption is a recursive definition of f that ... 0 First, we note that p|q_1 implies p=q (we don't even need Euclid's lemma to see this). Now assume that p|q_1q_2\ldots q_k\implies p|q_1 or p|q_2 or \cdots or p|q_k. Now consider the statement p|q_1q_2\ldots q_kq_{k+1}. Using Euclid's lemma, p must divide one of q_1q_2\ldots q_k or q_{k+1}. By our inductive hypothesis, we conclude that ... 2 If 4n^2+15n-1 is divisible by 9, then it's also divisible by 3; however$$ 4n^2+15n-1\equiv n^2-1\pmod{3} $$but n^2\equiv 1\pmod{3} if and only if 3\nmid n. So, for n=3k, the number 4n^2+15n-1 is not divisible by 3 and, of course, not divisible by 9 either. 2 It is not true buddy, take n=3. In general if n=3t it wont be true. Greetings! 3 The general idea is there, but you should consider exactly what you are proving. For every n>0, if \{x_i\mid i<n\} is a set of real numbers, then it has a minimal element (or minimum, since \Bbb R is linearly ordered). So to apply the WOP you need to consider the set$$\{n\in\Bbb N\mid\textsf{There exists a non-empty set of reals of size ...

1

Combinatorial Proof: For each $n\in\mathbb{N}_0$, the number of ways to tile an $1$-by-$n$ array with $1$-by-$1$ squares and $1$-by-$2$ dominos is $F_{n+1}$. Hence, the number of ways to tile an $1$-by-$(n+1)$ array in such a manner with at least one domino is given by $F_{n+2}-1$. Now, let $k$ be the earliest position of the dominos. For each $k$, we ...

1

For the base case you will need to use $n=1$ if you wish to prove for all $n\in\mathbb{Z^+}$. $$\sum_{i=1}^{n}{F_i} = \sum_{i=1}^{1}{F_i} = F_1 = 1$$ and $$F_{n+2}-1=F_3-1=2-1=1$$ Proving the base case. For the induction step (weak induction suffices, note that weak induction is a special case of strong induction), you can assume the IH (induction ...

3

We know that $F_{n+2} = F_{n+1} + F_n \implies F_n = F_{n+2} - F_{n+1}$, so ... $$\sum_{i=1}^nF_i = \sum_{i=1}^n\left(F_{i+2} - F_{i+1}\right)$$$$=\left(F_3 - F_2\right) + \left(F_4-F_3\right) + \dots + \left(F_{n+1} - F_{n}\right)+ \left(F_{n+2} - F_{n+1}\right)$$ $$= F_{n+2} + \left(F_{n+1} - F_{n+1}\right) + \dots + \left(F_{3} - F_{3}\right) - F_2$$ ...

-1

$$F_{3} = F_2 + F_{1} \\ F_{4} = F_3 + F_{2} \\ F_{5} = F_4 + F_{3}\\ ... F_{n} = F_{n -1} + F_{n-2}\\ F_{n+1} = F_n + F_{n-1}\\ F_{n+2} = F_{n+1} + F_{n}\\$$ Now just sum the right side and the left side. You'll get: $$\sum_{i=3}^{n+2}F_i = \sum_{i=2}^{n+1}F_i + \sum_{i=1}^{n}F_i$$ Then $$\sum_{i=3}^{n}F_i + F_{n+1}+ F_{n+2} = \sum_{i=2}^{n+1}F_i + ... 1 The proof you're presenting has an error in it (in the formula) and can't be used to demonstrate anything.  \frac{a^{(n-1)} \times a^{(n-1)} }{a^{(n-1)-1}} = \frac{1 \times 1}{1 \times a^{-1}} = a \neq \frac{1 \times 1}{1}  Back to the original question. Both the strong and weak principles can be used to proof theorems, the weak having limitation doesn't ... 1 If you want to have any chance of proving \forall n:\sum_{i=1}^n i=f(n), then of course it must hold that$$f(n+1)=\sum_{i=1}^{n+1}i=\left(\sum_{i=1}^n i\right) +(n+1)=f(n)+(n+1)$$For if this were not true, then the claim that \forall n:\sum_{i=1}^n i=f(n) is false, and hence cannot be proven (assuming consistency and bla bla bla). So yes, ultimately ... 3 Any property that satisfy exactly the integers contained in some interval [a,\infty), where a\le 0. For example: To have a real square root. To satisfy the inequality x^3+100>0. To be non-negative. Etc. 1 The axiom you are over-looking is not any of the semi-ring axioms (induction does not hold in any arbitrary semi-ring) but this axiom of the natural numbers: If S \subseteq \Bbb N and: a)\ 0 \in S\\b)\ x \in S \implies x+1 \in S (some texts write s(n) or x' instead of x+1, especially if addition has not yet been defined). then S = \Bbb N. ... 1 Let' clarify the concept on a specific example. We know that$$1+2+\cdots +n=\frac{n(n+1)}2.\tag 1$$Prove this statement a fake naive way: Observe that (1) is true for n=2. Indeed,$$3=1+2=\frac {2\times 3}2.\tag 2 Observe that you can prove the same for $n=3$ based on $(2)$ now: ...

Top 50 recent answers are included