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
votes
2answers
66 views

Proof that expression is integer, $\frac{(2n)!}{n!(n+1)!}$

can you help me with this excercises.. Proof that expression is integer, $$\frac{(2n)!}{n!(n+1)!}$$ I've tried for induction!! $p(1):\frac{(2)!}{2}=1 $ for $p(k)=\frac{(2k)!}{k!(k+1)!}$ for ...
2
votes
3answers
57 views

Proof that expression is integer, $\frac{(3n)!}{6^nn!}$

Can you help me with this exercises? Proof that expression is integer, $$\frac{(3n)!}{6^nn!}$$ I've tried for induction!! $p(1):\frac{(3)!}{6}=1 $ for $p(k)=\frac{(3k)!}{6^kk!}$ for ...
-1
votes
1answer
32 views

Use induction to prove the following equation: $2 + 6 + 10 + \cdots + (4n − 2) = 2n^2$ where $n \ge 1$ [on hold]

Use induction to prove the following equation: $2 + 6 + 10 + \cdots + (4n − 2) = 2n^2$ where $n \ge 1$
-6
votes
1answer
51 views

Proof by induction $2^n\times 2^n$ [duplicate]

Please help: Prove the following claim by induction: A checkerboard with $2^n\times 2^n$ squares from which one square has been removed can be covered exactly by "triominos" of the following form ...
-7
votes
0answers
49 views

Use method of Induction!! [duplicate]

Please help Question = Prove the following claim by method of induction: A checkerboard with 2^n x 2^n squares from with one square has been removed can be covered exactly by "triominos" of the ...
7
votes
1answer
64 views

Functional equation: Show $0\le f(n+1)-f(n)\le 1$ and find all $n$ such that $f(n)=1025$.

The function $f:\mathbb{N}\to \mathbb{R}$ satisfies all of $$\begin{align}f(1)&=1, \\ f(2)&=2,\\ f(n + 2) &= f(n + 2 − f(n + 1)) + f(n + 1 − f(n)) \tag{1} \end{align}$$ Show ...
0
votes
3answers
45 views

Use induction to prove that $F_n \ge \sqrt 2 ^n$ for $n \ge 6$

The Fibonacci sequence $F_0, F_1, F_2,\dots$ is defined by the rule $F_0=0, \ F_1=1, \ F_n = F_{n−1} + F_{n−2}$. Use induction to prove that $F_n \ge \sqrt 2 ^n$ for $n \ge 6$. So for the base case: ...
1
vote
2answers
63 views

“Proof” that $(2n)!$ is divisible by $2^n 5^{n-3}$ for $n\ge3$

Please explain, as clearly as possible, what is wrong with the following "proof" by induction that $\hspace{1.4 in}$$(2n)!$ is divisible by $2^n 5^{n-3}$ for $n\ge3$. (There clearly must be an ...
-6
votes
1answer
66 views

Checkerboard with one gap can be covered by triominos? [on hold]

A checkerboard with $2^{n}\times 2^{n}$ squares from which one square has been removed can be covered exactly by "triominos". Form is one square up with $2$ below them.
1
vote
4answers
64 views

Prove that $1^2 + 2^2 + … + (n-1)^2 < \frac {n^3} { 3} < 1^2 + 2^2 + … + n^2$

I'm having trouble on starting this induction problem. The question simply reads : prove the following using induction: $$1^{2} + 2^{2} + ...... + (n-1)^{2} < \frac{n^3}{3} < 1^{2} + 2^{2} + ...
2
votes
3answers
52 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
30 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 ...
25
votes
7answers
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
48 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
16 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
48 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
59 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
53 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
120 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 ...
-1
votes
2answers
56 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
26 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
76 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
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
42 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
74 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
65 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
177 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
52 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
100 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 ...