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

1
vote
1answer
34 views

Mathematical induction: using 3 cent and 7 cent stamps

Use mathematical induction (and proof by division into cases) to show that any postage of at least 12 cents can be obtained using 3 cent and 7 cent stamps. I thought this was the simple kind of ...
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 = ...
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 ...
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. ...
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 ...
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
116 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
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
63 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.
-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
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
37 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
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) ...
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
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 ...
-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
77 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
326 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!