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
2answers
27 views

100-level discrete maths, induction problem, prove $n^2 \ge 2n + 1$

I've just run into this problem, and was able to go as far, and understand the induction step up to the bolded section. The last part I found in the back of my book, italicized, I can't understand. ...
1
vote
1answer
14 views

Show that $\sum_{i=1}^{n}[\log_{2}(n/i)]$ is O(n), hint use Stirling's Approximation

Assume that n is a power of 2. Hint 1: Use induction to reduce the problem to that for n/2. Hint 2: Alternative hint -> use Stirling's Approximation. Im trying to solve this problem using the lime ...
2
votes
2answers
37 views

Bernoullis inequality proof

Hi I'm asked to do a proof for bernoullis inequality which is $(1+a)^n \geq 1+na$ where $a\geq-1$ I'm proving by induction by the way. So far these are my steps $(1+a)^1 \geq 1+a$ Then $(1+a)^k ...
14
votes
5answers
791 views

Fibonacci number identity.

How do I see that $f_{n+1}f_{n-1} = f_n^2 + (-1)^n$, $n \ge 2$, where $f_1 = 1$, $f_2 = 1$, and $f_{n+2} = f_{n+1} + f_n$ for $n \in \mathbb{N}$?
1
vote
3answers
43 views

Induction proof.

Homework question, so just a pointer would be nice, for starters. I'm trying to prove $2 \mid 5^{2n} - 3^{2n}$ by induction. I use $n=0$ as the base step, and assume $5^{2n} - 3^{2n} = 2k$ as my ...
0
votes
1answer
20 views

Prove the following using induction on d (matrices)

I manage to reach the step where I need to prove n = k + 1 but I am battling to complete the proof as I am not certain what to do with the exponents in my answer. I will run through the proof as I ...
1
vote
1answer
24 views

Theory of Computation Notation Proof

The Question: Show that if $f(n) = \mathcal{O}(g(n))$ and $g(n) = \mathcal{O}(f(n))$, then $f(n) = \Theta(g(n)).$ I know that since $\Theta$ is a stronger notation than $\mathcal{O}$, then: $f(n) = ...
1
vote
5answers
219 views

Proof by induction for “sum-of”

Prove that for all $n \ge 1$: $$\sum_{k=1}^n \frac{1}{k(k+1)} = \frac{n}{n+1}$$ What I have done currently: Proved that theorem holds for the base case where n=1. Then: Assume that $P(n)$ is ...
0
votes
1answer
22 views

Help with induction question

I'm trying to prove the following equation by induction, but my base case isn't working. for all n>2. For my base case I did n=3, and on the LHS I got 8/9 and the RHS I got 2/3. Helppp.
-1
votes
1answer
25 views

Use induction to prove that n! ≥ 2^(n−1) for for all integers n ≥ 1. [on hold]

Use induction to prove that n! ≥ 2^(n-1) for for all integers n ≥ 1. Hello everyone, I'm stuck on this problem right here $(k+1)! = 2^{(k+1)-1}$
0
votes
1answer
20 views

Trying to correctly write the proof using *strong* induction of the sum of the nth positive integer

I'm learning about proofs using induction and our professor want us to always use strong induction when giving proofs. In my understanding, strong induction is used to show the range of numbers you ...
-1
votes
2answers
72 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
60 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
35 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$
-7
votes
0answers
50 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
71 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
46 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
66 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
70 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
66 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
54 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? [closed]

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
50 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
41 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
54 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
56 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
44 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
26 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, ...