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

3
votes
2answers
184 views

Proving Rational Numbers are Countable in a Different Way

Prove that positive rational numbers are countable using the partitions: $P_i= \lbrace x \in \mathbb{Q}^+ | x= {p \over{q}}, p+q=i, \gcd(p,q)=1 \rbrace$ where $\gcd(p, q)$ is the greatest common ...
4
votes
3answers
137 views

Prove even integer sum using induction

This is a homework problem, so please do not give the answer away. I must prove the following using mathematical induction: $\forall n\in\mathbb{Z^+},\;2+4+6+\cdots+2n=n^2+n.$ This is what I ...
4
votes
2answers
75 views

Understanding this proof

I don't know how they come from the step prior to the last to the last. If somebody could explain what happens there, that would be appreciated. Thanks in advance!
1
vote
1answer
47 views

Upper Bounds Proof

The sequence $\left(s_n\right)_{n=1}^{\infty}$ is defined recursively as follows: let $s_1 = 1$, and then $s_{n+1} = \sqrt{1+2s_n}$ for $n \geq 1$. (So $s_1 = 1, s_2 = \sqrt{3}, s_3 = \sqrt{1+2\sqrt{3}...
0
votes
1answer
49 views

problem understanding induction proof for following recurrence sequence $\frac{a_{n-1}+a_{n-2}}{2}$

I've got this recurrence sequence and it's proof, but I'm stuck with the 2nd/3rd step in the induction step. $$a_0:=0, a_1:=1\\ a_n:= \frac{a_{n-1}+a_{n-2}}{2}$$ Show that for all $n\in N$: $a_n-a_{...
0
votes
0answers
18 views

Prove simple induction [duplicate]

Suppose we we have n straight lines on the plane such that no two of them are parallel and no three of them go through the same point. Prove that the number of different regions that are created by ...
1
vote
1answer
51 views

How does $H_{k}=\displaystyle\left[H_{k+1}-\frac{1}{k+1}\right]$?

I'm confused about one of the algebraic steps, In showing the $k+1$'th term, we have: \begin{align}\displaystyle\sum\limits_{j=1}^{k+1}H_{j} &= \displaystyle\sum\limits_{j=1}^{k}H_{j} + H_{k+1} ...
1
vote
1answer
49 views

Proof by induction: form of a polynomial

Problem: Any polynomial $P_n(x)$ can be written as $P_n(x)$=$\sum_{i=0}^n c_i \alpha_i(x) $ where $\alpha_i(x)$ is a polynomial of degree exactly $i$. Attempt: Base case ($n=1$): $P_1(x)=c_0+c_1(x)$ ...
2
votes
3answers
95 views

Proof using strong induction [duplicate]

I need to prove/show that $n^3 \leq 3^n$ for all natural numbers $n$ by strong induction. I have no clue where to begin!!!! :( I know how to do the beginning steps of showing that it's true for $k = 0$...
3
votes
3answers
90 views

Prove $(1 +\frac{ 1}{n}) ^ {n} \ge 2$

Using induction, I proved the base case and then proceeded to prove: $$(1 + \frac{1}{n+1}) ^ {n+1} \ge 2$$ given $$(1 + \frac{1}{n}) ^ n \ge 2$$ However, I'm stuck at this point and have no clue how ...
2
votes
2answers
53 views

Prove by Induction Summation

Prove by induction: Given that $f(x) = x^{-1}$, then the $k$-th derivative of $f$ is given by $f^{\langle k\rangle}(x) = (−1)^k \cdot k!\;x^{−(k+1)}$ for all $k ≥ 1$. How do I go about proving this? ...
9
votes
2answers
3k views

What exactly is the difference between weak and strong induction?

I am having trouble seeing the difference between weak and strong induction. There are a few examples in which we can see the difference, such as reaching the $k^{th}$ rung of a ladder and ...
0
votes
2answers
57 views

Prove that continued fractions are fractional linear transformations

Consider the continuous fractions defined inductively by $a_1=1+\frac{1}{x}, a_2=1+\cfrac{1}{1+\frac{1}{x}}, a_3=1+\cfrac{1}{1+\cfrac{1}{1+\frac{1}{x}}}, ...$ Prove that each $a_n$ is a fractional ...
0
votes
1answer
36 views

marix proof by induction

Given the matrix $A$ \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix} use proof by induction to show that $A^n$ for $n=1,2..$. is \begin{pmatrix} 2^n & 2^n - 1 \\ 0 & 1 \end{...
0
votes
1answer
64 views

Proving (n+1-k)(n-k) / 2 from P(n+1-k)

A part of a proof by strong induction implementation is : Given : $P(K) = k(k-1)/2$ How to arrive at $(n+1-k)(n-k) / 2$ from $P(n+1-k)$ ? Lecture screenshot (taken from MIT Mathematics for ...
4
votes
4answers
2k views

Why is “All horses have the same color” considered a false proof by induction? [duplicate]

Upon reading of All horses have the same color "paradox", I began to wonder a couple of things. First of all, to me the inductive step seems flawed. Just because I have $n$ white horses, does not ...
15
votes
6answers
1k views

Induction - Examples where the induction step is correct but the base case is always wrong [duplicate]

I'd like to present to my students some induction examples that always satisfy the inductive step but never the base case. It could be for natural numbers, graphs or anything else.
4
votes
2answers
46 views

Showing $4^m>2m^2 + 5m$ for $m\geq 3$ by induction

Show that $4^m>2m^2 + 5m$. I want to practice proving by induction. I know that this is not true for small values of $m$. So, the base case can be $m=3$. Then we have $$4^3 > 2(3)^2+5(3)$$ = $$...
2
votes
1answer
119 views

Predicated needed for proof using structural induction

I have a set, $F$, of boolean formulas defined inductively as follows: $X_{i} \in F, \: \forall i \in \mathbb{N} \: \text{(variables)}\\ A \in F \implies \neg A \in F\\ A, B \in F \implies A \land B \...
1
vote
2answers
497 views

How to prove what amounts of postage can be formed with normal mathematical induction?

This is similar to my other question Strong induction but it addresses standard mathematical induction. Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 ...
4
votes
5answers
81 views

Prove $7$ divides $13^n- 6^n$ for any positive integer

I need to prove $7|13^n-6^n$ for $n$ being any positive integer. Using induction I have the following: Base case: $n=0$: $13^0-6^0 = 1-1 = 0, 7|0$ so, generally you could say: $7|13^k-6^k , ...
5
votes
2answers
85 views

Proof by induction that $\frac1{n+1}+ \frac1{n+2}+\cdots+\frac1{2n}=1-\frac{1}{2}+\cdots+\frac{1}{2n-1}-\frac{1}{2n}.$

Prove that for any positive integer, $$\frac1{n+1}+ \frac1{n+2}+\cdots+\frac1{2n} = \left(1-\frac1{2}\right)+\left(\frac1{3}-\frac1{4}\right)+\cdots+\left(\frac1{2n-1}-\frac1{2n}\right).$$ I have ...
46
votes
12answers
7k views

Proof that every number ≥ $8$ can be represented by a sum of fives and threes.

Can you check if my proof is right? Theorem. $\forall x\geq8, x$ can be represented by $5a + 3b$ where $a,b \in \mathbb{N}$. Base case(s): $x=8 = 3\cdot1 + 5\cdot1 \quad \checkmark\\ x=9 = 3\cdot3 ...
2
votes
5answers
135 views

Prove by induction $(1+x)^n≥1+nx, ∀x>-1, ∀n∈N$ [duplicate]

I think I understand how induction works, but I wasn't able to justify all the steps necessary to prove this proposition: $(1+x)^n≥1+nx, ∀x>-1, ∀n∈N$ One thing that confuses me is that I don't ...
3
votes
4answers
131 views

Prove by mathematical induction that: $\forall n \in \mathbb{N}: 3^{n} > n^{3}$

Prove by mathematical induction that: $$\forall n \in \mathbb{N}: 3^{n} > n^{3}$$ Step 1: Show that the statement is true for $n = 1$: $$3^{1} > 1^{3} \Rightarrow 3 > 1$$ Step 2: Show ...
0
votes
1answer
43 views

Prove Harmonic Series Statement

Show that for all n ≥ 0: H2n ≤ 1 + n I have already done it for bigger or equal to one to prove that it eventually reaches infinity but how would I do this one?
0
votes
4answers
43 views

How to do a Proof by Induction

I need to prove the following statement below by using induction. The problem is I have no clue what induction is and how I can approach it. Thanks! Prove by Induction: $$3 + 7 + 11 + \cdots+ (...
1
vote
2answers
191 views

Prove a matrix Question by Induction

I am struggling with this question. I get to to a certain point and then don't know what to do. So heres what I do. Given: A= $$ \begin{bmatrix} 2 & 0 \\ -1 & 1 \\ ...
5
votes
8answers
190 views

Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.

$$10^{2(k+1)}-1 = 10^{2k+2}-1=10^{2k}\cdot10^{2}-1$$ I feel like there's something in that last part that should make it work, but I can't grasp it. Am I missing something obvious? Am I going in the ...
1
vote
0answers
488 views

Proving a recursive algorithm as correct using induction

My objective is to give a recursive algorithm for finding the maximum of a finite set of integers, "making use of the fact that the maximum of n integers is the larger of the last integer in the list ...
1
vote
1answer
43 views

How to prove by induction the following :

How to prove using induction the following is true : Let $X_1, X_2,\ldots,X_n$ be i.i.d r.v. that are distributed exponentially with $\lambda$. Then $ \forall n \ge 3$ $$ \Pr(X_1 > \sum_{k=2}^n ...
2
votes
2answers
671 views

How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ...
1
vote
5answers
98 views

How to conclude 4 + 4k is divisible by 8 in proof by induction?

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 35, pg 330]. Problem: a) Use mathematical induction to prove that $n^2$ - 1 is divisible by 8 whenever n is an odd ...
0
votes
3answers
134 views

Discrete Math-Proof by Induction

Could someone please check my work and see if this is correct? Thanks. For all integers $n \geq 1$, prove the following statement using mathematical induction. $$1+2^1+2^2+...+2^n = 2^{n+1}- 1$$ 1) ...
1
vote
2answers
83 views

Strong Induction for a sequence inequality?

On the previous midterm, there was a question that I couldn't solve. It gave us this sequence The sequence $$a_0, a_1, a_2,... $$is defined by $$a_0 = 1,$$ and for all integers $$n > 0,$$ $$a_n = ...
0
votes
2answers
260 views

Prove that for every integer $n\geq 0$, $1+3n\leq 4^n$.

Prove that for every integer $n\geq 0$, $1+3n\leq 4^n$. Proof: Let the property $P(n)$ be the inequality $$1+3n\leq 4^n.$$ Establishing $P(0)$, we see that $1+3(0)=1$ and $4^0=1$, hence $P(0)$ is ...
2
votes
2answers
65 views

How to generalize the calculating of at least one event occurring for more than two events?

In this answer, we are given the solution for calculating the probability of at least of of two events occurring. How can we generalize that for 3 or more events? For example, what is the ...
1
vote
3answers
68 views

Induction - how to prove like $s(n) \Rightarrow s(n-1)$

Until now it was all ok for proving the statements like $S(n) \Rightarrow S(n+1)$, however I've encountered a question that says: Let $S(n)$ be an open statement such that $S(n)$ is true for ...
1
vote
2answers
48 views

When is this sequence of positive integers a square?

I have two sequences below, and I would like to know for which $n$ the number $k_n$ is a square. $$ \begin{align} k_1 &= 9\\ t_1 &= 1\\ k_{n+1} &= 9k_n + 80t_n\\ t_{n+1} &= k_n + ...
1
vote
0answers
123 views

What really is inductive reasoning?

I am looking for concrete information on "induction" in the old sense of the word. Now it is used to refer to proof by "mathematical induction"; however, I am aware that it also means inductive ...
1
vote
3answers
48 views

Proof with derivatives (most likely induction)

Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be given by an equation $$f(x)=(\sin(x^3))^3$$ With use of the fact that function f is odd, show that all derivatives in a form $f^{(2n)}(0)$ for $n=0,1,2, \...
2
votes
2answers
78 views

For any integer $n\geq2$, prove that $\displaystyle\sum\limits_{i=1}^{n-1}i(i+1) = \frac{n(n-1)(n+1)}{3}.$

For any integer $n\geq2$, prove that $\displaystyle\sum\limits_{i=1}^{n-1}i(i+1) = \frac{n(n-1)(n+1)}{3}.$ Let $P(n)$ be the formula $\displaystyle\sum\limits_{i=1}^{n-1}i(i+1) = \frac{n(n-1)(n+1)}{...
4
votes
8answers
84 views

Prove by induction that $3^{3n+1} + 2^{n+1}$ is divisible by 5

How do I do this? I've tried using logarithms, factoring, but nothing seems to work.
0
votes
2answers
473 views

Induction proof using Pascal's Identity: $\binom{n}{0}+\binom{n}{i}+…+\binom{n}{n}=2^n$

Prove by induction that for all $n ≥ 0$: $\binom{n}{0}+\binom{n}{i}+....+\binom{n}{n}=2^n$ We should use pascal's identity Base case: $n=0$ LHS: $\binom{0}{0}=1$ RHS: $2^0=1$ Inductive step: ...
0
votes
0answers
34 views

Proof by induction- The sum of the cubes of the first n positive integers [duplicate]

I am having trouble with this proof by induction. The sum of the cubes of the first $n$ positive integers can be computed by the following formula: $\sum_{k=1}^{n}k^3= 1^3 + 2^3 + . . . + n^3 = \...
3
votes
1answer
171 views

prove inequality by induction — Discrete math

Prove by induction that $∀n ≥ 3$ : $n^{2} + 1 ≥ 3n$ So I know I need to find my base case, would it be: $n=3$ Then calculate the RHS and LSH RHS:$3(3)=9$ LHs: $3^{2} + 1= 10$ we see that the LHS is ...
4
votes
6answers
80 views

Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$

Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$ Step 1: Show that the statement is true for n = 1: $4^{2 \cdot 1} + 4 = 20$ Since $20~|~20$, the base case is ...
2
votes
2answers
65 views

How to use Induction with Sequences?

I have posted this similar question here, but with no hopes. I would just like to know: Most of the solution I have no issue with. Look at where they say: "Choose a representation $(n - 3^m)/2 = ...
1
vote
2answers
44 views

Showing that if $xf(x)=\log x$ for $x>0$ then $f^{(n)}(1)=(-1)^{n+1}n!\bigg(1+\dfrac12+\dfrac13+\ldots+\dfrac{1}{n}\bigg)$

Let $f(x)$ be a function satisfying $$xf(x)=\log x$$ for $x>0$. Show that $$f^{(n)}(1)=(-1)^{n+1}n!\bigg(1+\dfrac12+\dfrac13+\ldots+\dfrac{1}{n}\bigg),$$ where $f^{(n)}(x)$ denotes the $n$th ...
3
votes
2answers
66 views

Mathematical induction problem with inequality

I have the following problem where n is a positive integer $(n >= 1)$: Prove that $\frac{1}{2n}\le\frac{1*3*5*...*(2n-1)}{2*4*...*2n}$ I know that I must start with the basic step showing that $P(...