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

7
votes
5answers
412 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 = ...
1
vote
1answer
39 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 ...
0
votes
0answers
11 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. ...
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
40 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
55 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 ...
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 ...
3
votes
4answers
112 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: ...
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 ...
0
votes
1answer
48 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 ...
-4
votes
1answer
59 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$$
-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!}$$
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
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.
-1
votes
0answers
20 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
vote
2answers
44 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
71 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
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 ...
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 ...
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 : ...
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
63 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) ...
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
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 ...
10
votes
1answer
174 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 ...
-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$ ...
1
vote
3answers
38 views

Show that $1/\sqrt{1} + 1/\sqrt{2} + … + 1/\sqrt{n} \leq 2\sqrt{n}-1$ [duplicate]

Show that $1/\sqrt{1} + 1/\sqrt{2} + ... + 1/\sqrt{n} \leq 2\sqrt{n}-1$ for $n\geq 1$ I attempted the problem but I get stuck trying to show that if the statment is true for some $k\geq1$ then $k+1$ ...
0
votes
1answer
35 views

Induction proof question

Show by induction that for all integers n $\ge$ 1 $$ \sum_{i=1}^n i3^i = \frac{3(2n3^n-3^n+1)}{4} $$ Starting with n = 1 will give me LHS = 3 and RHS = 3. Inserting n = p gives $$\sum\limits_{i=1}^p ...
3
votes
4answers
98 views

Prove that $n!>n^2$ for all integers $n \geq 4$.

I am working on induction problems to prep for Real Analysis for the fall semester. I wanted proof verification and editing suggestions for part (a), and assistance understanding part (b). For part ...
2
votes
2answers
38 views

Can I use induction by $|V|$ here?

Show that any connected, undirected graph $G = (V,E)$ satisfied $|E|≥|V|-1$. Can I use math induction by $n = |V|$ here (remove and add vertex)?
4
votes
1answer
34 views

Principle of mathematical induction to prove well ordering principle for set of rationals.

I am not being able to find what is wrong in this proof. statement: For any set of rationals there is a least element in the set. Hypothesis: $p(k)$=For set of k rationals there exist a least ...
1
vote
0answers
28 views

Proving recursive formula via induction leads to extra term?

I have been asked the following question, and despite spending the last 30 minutes on it, have not come up with a good result: Define f(1) = 2, and f(n) = f(n-1) + 2n for all n ≥ 2. Find a ...
2
votes
2answers
76 views

Proving that $P\left ( \bigcup_{i=1}^{n}A_{i} \right )\leq \sum_{i=1}^{n}P(A_{i})$ by induction

Proposition 1: Let $A_{1},\dots, A_{n}$ be events in the probability space $(\Omega,\mathcal{F},P)$. Then $$P\left ( \bigcup_{i=1}^{n}A_{i} \right )\leq \sum_{i=1}^{n}P(A_{i}).$$ Let's start with a ...
0
votes
0answers
27 views

Proof for maximum number of leaves in a tree with a given hopping distance

Hi I need help to prove the following for tree graphs which I believe is true: A tree with hopping distance $k$ (i.e. the most number of edges that any two vertices are apart) and n leaves either has ...
3
votes
7answers
117 views

Proving $\frac{1}{1\cdot3} + \frac{1}{2\cdot4} + \cdots + \frac{1}{n\cdot(n+2)} = \frac{3}{4} - \frac{(2n+3)}{2(n+1)(n+2)}$ by induction for $n\geq 1$

I'm having an issue solving this problem using induction. If possible, could someone add in a very brief explanation of how they did it so it's easier for me to understand? $$\frac{1}{1\cdot3} + ...
27
votes
1answer
324 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 ...
-3
votes
2answers
73 views

Proving $25^{n+1} -24n +5735$ is always divisible by $576$ [closed]

Prove $25^{n+1} -24n +5735$ is always divisible by $576$ using mathematical induction. Not able to simplify the expression after replacing $n=k+1$ Please help... Thanks!
2
votes
2answers
104 views

I have to prove by mathematical induction that $\frac{(2n)!}{n!(n+1) !}$ is a natural number for all $n\in\mathbb{N}$.

I have to prove by mathematical induction that $$\frac{(2n)!}{n!(n+1) !}$$ is a natural number for all $n\in\mathbb{N}$. Any help would be really awesome.
0
votes
1answer
33 views

Check my solution: For the recurrence $a_{n+3}=a_{n+2}+a_{n+1}+a_n$ where $a_1=a_2=a_3=1$, prove that $a_n\leq 2^{n-2}$.

I need help with verifying my solution for the homework question: For the recurrence $a_{n+3}=a_{n+2}+a_{n+1}+a_n$ where $a_1=a_2=a_3=1$, prove that $a_n\leq 2^{n-2}$, $\forall n>1$ ...