For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

learn more… | top users | synonyms

0
votes
1answer
25 views

How do you symbolically represent the general principle of induction? [on hold]

Normally a specific function is given, and then it would be asked to prove the validity of that specific function with induction. But how do you logically represent the general principle of induction ...
19
votes
4answers
1k views

We all use mathematical induction to prove results, but is there a proof of mathematical induction itself?

I just realized something interesting. At schools and universities you get taught mathematical induction. Usually you jump right into using it to prove something like $$1+2+3+\cdots+n = ...
3
votes
4answers
115 views

Proving $\frac{n^n}{3^n} < n!$ for $n\ge6$ by induction

How would I prove this using mathematical induction: $\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$. Here is what I have tried: $\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$ Base case: ...
1
vote
1answer
42 views

Using induction more than once in a proof

Is it possible to use induction twice or more in a proof? For instance, say we wished to prove the following proposition by induction: Proposition Suppose $x>3$ and $y<2$. Then $x^2 ...
10
votes
0answers
239 views
+100

Cauchy induction: are there examples of cases where choosing an integer other than $2$ is a better strategy?

Cauchy induction, sometimes called backwards induction, works as follows: show that $p(1)$ is true show that $p(n)$ implies $p(2n)$ (which inductively implies $p(2^n)$ is true) show that $p(n)$ ...
0
votes
0answers
14 views

Structural induction over types that accept functions, in Coq

If you define an inductive type in Coq with a constructor that accepts a function mapping to that type, you get a somewhat odd induction rule. ...
9
votes
2answers
223 views

Is transfinite induction needed to remove all the elements from an uncountable set?

Given any uncountable set S, would I need to use transfinite induction to prove if I remove single elements recursively, I will be left with the empty set? It seems like this can be thought of as an ...
0
votes
3answers
40 views

doubt about the solution to an induction problem exercise [duplicate]

I need to prove that $5^n-1$ is divisible by $4$, $\forall n \in \mathbb{N}$. So for the inductive step I know that: $$5^{n+1} -1= 5\times5^n -1$$ but how do I get from there to: $$(5^n -1) + ...
5
votes
1answer
45 views

Stating the induction hypothesis

I would like to ask about the best way to state the induction hypothesis in a proof by induction. Just to use a concrete example, suppose I wanted to prove that $n!\ge 2^{n-1}$ for every positive ...
0
votes
1answer
16 views

Equivalence of definitions of the axiom of induction.

Definition 1: $(0\in S, n\in S \implies n+1\in S) \implies n\in S \forall n≥0$. Definition 2: $(P(0), P(n)\implies P(n+1)) \implies P(n) \forall n≥0$. To prove the equivalence of these ...
-1
votes
2answers
56 views

Prove by induction and recursion that $n!=n(n-1)(n-2)…(3)(2)(1). $

Prove by induction and recursion that $n!=n(n-1)(n-2)...(3)(2)(1). $ We can start with the definition of factorial with recursion: $$n!= \left\{\begin{align}1\quad \text{for}\quad ...
0
votes
0answers
16 views

What are good resources to self-study coinduction

I have studied induction and structural induction in computer science. Assuming familiarity with induction and proof techniques, what are some good resources to familiarize myself with co-induction. I ...
0
votes
0answers
17 views

Principle of Induction and F-closure

I am reading Types and Programming Languages by Benjamin Pierce and I came across the following Principle of Induction: If X is F-closed then $\mu$F $\subseteq$ X. Definition of F-closed. Let U ...
1
vote
1answer
57 views

Understanding a step in this proof by induction

Here's an example I discovered in a book. Prove inequality when $a\ge-1$:$$(1 + a)^n \ge 1 + na.$$ Let's use mathematical induction. Then $n = 1$ left and right parts are equals. Let's ...
1
vote
1answer
48 views

A counterexample of induction on integers?

What could be an example of a property $P(n)$ pertaining to an integer $n$ such that $P(0)$ is true, and that $P(n)$ implies $P(n++)$ for all integers $n$, but that $P(n)$ is not true for all integers ...
0
votes
1answer
50 views

Property for the natural numbers.

This question is inspired by another question I had, where I wanted to prove something about the natural numbers. Often in analysis books I see some proofs, where they use the natural numbers, but it ...
0
votes
1answer
15 views

How many ways are there to express a natural as a sum of 3 others—but by induction?

I have figured out an (inductive?) process, but I cannot express it formally: There is always one possibility where $n$ is in the first place of our 3-tuple: $[n~~0~~0]$. Then I can subtract $k~(\leq ...
1
vote
1answer
37 views

How to prove that at Complete Binary Tree (CBT) at height $h$ we have $2^h$ leaves

I try to prove it by induction, please tell me if I'm right... The induction assumption - For every CBT at height $h$ there is $2^h$ leaves. The base of the induction is right (I'm writing this proof ...
1
vote
3answers
765 views

How can it be proved that the geometric mean function is concave?

A function $f: \mathbb R ^n \rightarrow \mathbb R $ is said to be concave if $\forall x,y \in \mathbb{R}^n, \forall \lambda \in [0,1]$ we have $ \lambda f(x) + (1-\lambda)f(y) \le f( \lambda x + ...
0
votes
1answer
55 views

Proving well-ordering property of natural numbers without induction principle?

In Munkres, Topology, he has this way of proving the well ordering property for the natural numbers: He assumes he can work with the real numbers from the for the real numbers Then he defines an ...
-5
votes
1answer
62 views

Proof that ${2n \choose n}= \frac {1\cdot3\cdot5\cdots(2n-1)}{n!}2^n$ [closed]

HELP ME WITH THIS EXERCISES.. Proof for induction that $${2n \choose n}= \frac {1\cdot3\cdot5\cdots(2n-1)}{n!}2^n$$
-2
votes
0answers
21 views

Second principle of induction implies first principle of induction. [closed]

Can anyone give me a proper proof that Second principle of mathematical Induction(PCI) aka "strong" form of induction implies First principle of mathematical Induction(PMI) aka "weak fom"
-1
votes
2answers
53 views

Proof that expression is integer [duplicate]

hi guys can you help me with this? Proof that expression is integer $$\frac{(2n)!}{2^nn!}$$
1
vote
3answers
75 views

Discrete mathematics question

$$(n+1)^2+(n+2)^2+(n+3)^2+\dots+(2n)^2=\frac{n(2n+1)(7n+1)}{6}$$ Prove the statement using mathematical induction.
0
votes
2answers
25 views

Induction Proof 3

I want to prove this simple fact: $\frac{n}{n+1} \geq \frac{1}{2}$ for all $n\in \mathbb{N}$. Would this suffice: Proof by induction: Base case: let $n = 1$, we have the result. Inductive step: ...
1
vote
3answers
41 views

Proving: $\frac{2x}{2+x}\le \ln (1+x)\le \frac{x}{2}\frac{2+x}{1+x}, \quad x>0.$

$$\begin{equation}\frac{2x}{2+x}\le \ln (1+x)\le \frac{x}{2}\frac{2+x}{1+x}, \quad x>0\end{equation}$$ I found this inequality in this paper: http://ajmaa.org/RGMIA/papers/v7n2/pade.pdf (Equation ...
0
votes
2answers
25 views

Show there exists an integer $L<m\leq K$ such that $m/n$ is an upper bound but $(m-1)/n$ is not

I'm trying to prove the following: "Let $E$ be a non-empty subset of $\mathbb{R}$, let $n \geq 1$ be an integer, and let $L<K$ be integers. Suppose that $K/n$ is an upper bound for $E$, but that ...
1
vote
2answers
45 views

The pattern in mathematical induction proofs

When given a statement to be proven by mathmatical induction the statement tends to look like this $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$ so going about the proof. 1) Prove the base case ...
1
vote
1answer
37 views

Induction Proof - Primes and Euclid's Lemma

I'm having some trouble with this proof. Here's the question: Use mathematical induction and Euclid's Lemma to prove that for all positive integers $s$, if $p$ and $q_1, q_2, \dotsc, q_s$ are prime ...
3
votes
2answers
73 views

$9 \mid 4n^2 + 15n - 1$ for $n \in \mathbb N$

How to prove by induction that $9 \mid 4n^2 + 15n - 1$ for every $n \in \mathbb N$? For $n = 1$ $4 \cdot 1^2 + 15 \cdot 1 - 1 = 18$ For $n \ge 2$ If $4n^2 + 15n - 1 = 9k$ then $4(n+1)^2 + 15(n+1) ...
1
vote
1answer
36 views

Use the Well Ordering Principle to prove that every finite, nonempty set of real numbers has a minimum element

This is a textbook problem. Here's my "proof": Assume for contradiction there exists a finite, nonempty set of real numbers which doesn't have a least element, call it $C$; suppose there are $n$ ...
3
votes
4answers
84 views

Fibonacci proof question $\displaystyle \sum_{i=1}^nF_i = F_{n+2} - 1$

The sequence of numbers $F_n$ for $n \in N$ defined below are called the Fibonnaci numbers. $F_1 = F_2 = 1$, and for $n \geq 2$, $F_{n+1} = F_n + F_{n-1}$. Prove the following facts about the ...
1
vote
3answers
822 views

Yet another confusion about Strong vs Weak Mathematical Induction - Wrong Proof?

In Mathematics literature, I am under the impression that there are at least two (non-trivially different) definition of Mathematical induction. I am assuming one is a weak form and the other is ...
2
votes
2answers
62 views

On the inner workings of induction?

I always had some doubts on the inner workings of induction. So I decided to make a little experiment. I am familiar with the proof that the sum of the first $n$ integers is $\cfrac{n(n+1)}{2}$ so I ...
1
vote
3answers
40 views

Question about proving with Mathematical Induction (some confusions on the concept)

While proving a statement of $f(n)$ using mathematical induction we do the following- we prove it for some natural number which satisfies the condition of $n$. We assume it true for some $k$. Then ...
27
votes
1answer
325 views

Uses of “Collatz induction”?

The Collatz conjecture is equivalent to the following "induction principle": If $P(0) \land P(1) \land (\forall{x} P(3 \cdot x + 2) \implies P(2 \cdot x + 1)) \land (\forall x P(x) \implies P(2 \cdot ...
0
votes
2answers
25 views

Proving guess wrong used for substitution method

Following is my recurrence relation : $T(n) = 2T(n−1) + c_1$. Complexity: $O(2^N)$. I want to prove it by substitution method/ mathematical induction (You can get insight of it from : ...
3
votes
4answers
2k views

Proof by induction; $a^n$ divides $b^n$ implies $a$ divides $b$

I want to prove by induction that $a^n \mid b^n$ implies that $a \mid b$ holds for all integers $n\geq 1$. Clearly for $n=1$ this is true, since if $a \mid b$, then $a \mid b$. Suppose this is true ...
0
votes
4answers
41 views

Does $(p(0) \wedge (P(n) \implies P(n-1))) \implies P(n) \forall n\leq 0$? [duplicate]

Does $(p(0) \wedge (P(n) \implies P(n-1))) \implies P(n) \forall n\leq 0$? In other words, what I'm asking is, can I use the axiom of induction for negative numbers? Why/why not? E: This is not a ...
0
votes
1answer
34 views

What is wrong with this inductive proof?

I have found a startling proof by induction which is clearly wrong. Let L(n) represent Lucas numbers. L(0)=2, L(1)=1 L(n) = L(n-1) + L(n-2) Let F(n) denote a Fibonacci number. F(0) = 0, F(1) = 1, ...
0
votes
1answer
64 views

Find the mistake of the inductive proof for $r^n=1$

Find the mistake in the following proof that purports to show that every nonnegative integer power of every nonzero real number is 1. Let r be any nonzero real number and let the property P(n) ...
4
votes
2answers
100 views

Proving $\sum_{i=0}^n 2^i=2^{n+1}-1$ by induction.

Firstly, this is a homework problem so please do not just give an answer away. Hints and suggestions are really all I'm looking for. I must prove the following using mathematical induction: For ...
10
votes
1answer
175 views

Prove $\sum\limits^m_{k=0} \frac{2n-k\choose k}{2n-k\choose n}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}=\frac{n\choose m}{2n-2m\choose n-m}2^{n-2m}$ for-

Let $n$ be a positve integer. Prove that$$\sum\limits^m_{k=0} \frac{2n-k\choose k}{2n-k\choose n}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}=\frac{n\choose m}{2n-2m\choose n-m}2^{n-2m}$$ for each non-negative ...
4
votes
1answer
856 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
0
votes
1answer
27 views

Strong induction on property of integers involving sets

Let property $P(n)= \begin{cases} \text{if $n$ is even, then any sum of $n$ odd integers is even} \\ \text{if $n$ is odd, then any sum of $n$ odd integers is odd} \end{cases}$ We need to show that ...
0
votes
1answer
34 views

solving for the inductive step in a proof by induction

I have no trouble solving for the base case. I need help solving the inductive step. I know that the nth line creates n new regions. But I don't know if that's based on intuition or if I have to ...
8
votes
2answers
221 views

Real Induction Over Multiple Variables?

I've seen in several different places* that one can use normal mathematical induction to prove the truth of a statement that relies not on just one variable (say, $x$,) but multiple variables (for ...
-1
votes
0answers
27 views

Proof by induction need help stuck [duplicate]

Hi I'm stuck on this question and need help. I got $x_1=\frac{1}{2}; x_2=\frac{2}{3}; x_3=\frac{3}{4}; x_4=\frac{4}{5}$ and don't know how to do part 2 - use proof by induction.
1
vote
2answers
51 views

Induction proving for $3^{n}+1 | 3^{3n}+1$

I find myself in difficult situation, it stays that I need to prove this $3^{n}+1 | 3^{3n}+1$ by induction and I don't know how to. It is trivially to calculate, that for every $n$ ...
10
votes
2answers
191 views

Proving that $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{100}}<20$

How do I prove that: $$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{100}}<20$$ Do I use induction?