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

4
votes
5answers
49 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 , ...
4
votes
2answers
71 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 ...
44
votes
12answers
6k 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
87 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
91 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
35 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
36 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
61 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
127 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
117 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
27 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 ...
1
vote
2answers
73 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
53 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
52 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) ...
0
votes
2answers
42 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
51 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)$ ...
2
votes
2answers
20 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
66 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
40 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
44 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
39 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
68 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) = ...
3
votes
8answers
80 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
61 views

Induction proof using Pascal's Identity

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
30 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
52 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
74 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
56 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
35 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
50 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 ...
1
vote
1answer
60 views

Proving something about the sequence of powers of 3 mod 10. Oh boy

Given the sequence $t_0=3, t_1=3^3,...$ so that $t_{n+1}=3^{t_n}$, prove $t_{k+1} \equiv t_k \mod 10^n$ for all integers $n \leq k$ My work so far: I thought it was a pretty obvious case for ...
1
vote
3answers
42 views

How to prove $2^{n+1} * 2^{n+1} = (2^n*2^n)+(2^n*2^n)+(2^n*2^n)+(2^n*2^n)$

Below diagram is used as part of a proof of induction to prove that $E$ a way to tile a $2^n * 2^n$ region with square missing : What is the proof that $2^{n+1} * 2^{n+1}$ = ...
1
vote
2answers
49 views

Proof by exhaustion:

We are given that a polynomial f(x) has integer coefficients. The coefficient of x^4 being 1. One root of it is ($\sqrt{2}+\sqrt3$). How do we find the other roots? I tried using long division, it ...
5
votes
6answers
123 views

Proving that $7^n(3n+1)-1$ is divisible by 9

I'm trying to prove the above result for all $n\geq1$ but after substituting in the inductive hypothesis, I end up with a result that is not quite obviously divisible by 9. Usually with these ...
0
votes
2answers
126 views

Using induction to study the sequence $\sqrt{6} , \sqrt{6 +\sqrt{6}}, \dots$ [closed]

For the given sequence; $\sqrt{6} , \sqrt{6 +\sqrt{6}},\sqrt{6+\sqrt{6+\sqrt{6}}} $ ... Use induction to show the sequence is bounded above by 3 Use induction to show $x_n $ is increasing Find the ...
0
votes
1answer
54 views

Proving a function by induction [duplicate]

Let $f(n)$ be the function defined by $$ f(n) = \frac 1{\sqrt{5}} \left[ \left(1+\sqrt{5}\over2\right)^n- \left(1-\sqrt{5}\over2\right)^n \right] $$ How do you prove that $f(n) = f(n+2) - f(n+1)$ ...
2
votes
3answers
66 views

Prove $k^2>k+1$ by induction

How would you prove that: $$n^2>n+1 \text{ for } n\ge2$$ using induction? Progress The base is clear, and after that I have assumed $n=k$ and I am trying to prove $(k+1)^2>k+2$ , but I ...
3
votes
2answers
56 views

Prove by mathematical induction that $\forall n \in \mathbb{N} : \sum_{k=1}^{2n} \frac{(-1)^{k+1}}{k} = \sum_{k=n+1}^{2n} \frac{1}{k} $

Prove by mathematical induction that: $$\forall n \in \mathbb{N} : \sum_{k=1}^{2n} \frac{(-1)^{k+1}}{k} = \sum_{k=n+1}^{2n} \frac{1}{k} $$ Step 1: Show that the statement is true for $n = 1$: LHS = ...
0
votes
2answers
150 views

Induction Question. Suppose there are n teams in a football league

how can i prove this Let n > 1 be an integer. Suppose there are n teams in a football league and every two teams have played against each other exactly once with no ties. Prove that it is possible to ...
0
votes
3answers
62 views

Prove that a sequence is increasing [duplicate]

A city's population in the $n^{th}$ year is denoted by $x_n$ (in millions). If, $\forall n \in \mathbb N^+$, we have: $x_1 = \frac34$, $x_{n+1} = 2x_n - x_n^2$, show that as $n \to \infty$, the ...
1
vote
2answers
106 views

Induction Proof: $\frac{1\cdot 3\cdots (2n-1)}{2\cdot 4\cdots (2n)} \geq \frac{1}{2n}$

Need help proving with induction that $\displaystyle \frac{1\cdot3\cdot5\cdot7...(2n-1)}{2\cdot4\cdot6\cdot8...\cdot2n} \ge \frac 1{2n}$ for all natural numbers $n$. I just can't even get started with ...
3
votes
2answers
64 views

Proving $2^n > (n+1)^2$ for $n\geq 6$ by induction.

So here is what I have to prove by induction: $2^n\gt(n+1)^2$ for $n\ge6$ So, first lets say $n=6$ $$2^6\gt(6+1)^2$$ $$64\ge49$$ Now, assume $n=k$ $$2^k\gt(k+1)^2\text{ for } k\ge6$$ Prove ...
0
votes
1answer
36 views

Let $f(x)=(x^2-1)^n$. Prove that for $r=0,1, … ,n$, $f^{(r)}(x)$ is a polynomial with value $0$ at no fewer than $r$ distinct points on $(-1,1)$.

Let $f(x)=(x^2-1)^n$. Prove that for $r=0,1, ... ,n$, $f^{(r)}(x)$ is a polynomial whose value is $0$ at no fewer than $r$ distinct points on $(-1,1)$. In other words, prove that $f^{(n)}(x)$. I ...
2
votes
2answers
86 views

Is this statement of Mathematical Induction correct?

Theorem: Principle of Mathematical Induction For each natural number $n$, let $P(n)$ be a statement. If $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ for every $k \geq 2$ Then $P(n)$ is true for ...
1
vote
1answer
26 views

Validity of Induction for a Summation

To prove the binomial identity $$\sum_{m=k}^{n-1}\binom{m}{k} = \binom{n}{k+1}$$ will an inductive method on $n-1$ be valid? Specifically, if we prove the base case where $n-1 = 0$, to determine it ...
0
votes
1answer
57 views

Number Theory using an induction proof

Prove that the inequality $$\left(1+\frac{1}{n}\right)^n > \frac{9}{4}$$ holds for all integers $n$ beyond a certain point. I must show that it is true for all $n>3$. but I am having difficult ...
1
vote
2answers
46 views

Proof $\frac{a_n^2+a_{n+1}^2+1}{a_{n}a_{n+1}} $ is constant

I would appreciate if somebody could help me with the following problem: Question: Defined by $a_{1} =1,a_{2}=2$ and $a_n a_{n+2}=a_{n+1}^2+1(n\geq 1)$ Proof. ...
6
votes
2answers
132 views

Prove that $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$.

Problem: Prove that $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$. My work: So I think I have to do a proof by induction and I just wanted some help editing my proof. My ...
2
votes
1answer
51 views

Peano's Axioms and Induction

I was reading Landau's Foundations of Analysis. He starts his construction of number systems by stating five axioms. My question is related to the fifth, the axiom of induction: Let there be given a ...
0
votes
0answers
18 views

If $s_{k,m}(n) =\sum_{i=n+1}^{kn+m} \frac1{i} $ show that for $k \ge 2m+1$, $s_{k,m}(n+1)>s_{k,m}(n)$ and $s_{k,m}(n+1)-s_{k,m}(n) <\frac1{n(n+1)} $

Let $s_{k,m}(n) =\sum\limits_{i=n+1}^{kn+m} \frac1{i} $. Show that, for $k \ge 2m+1$, $s_{k,m}(n+1)>s_{k,m}(n)$ and $s_{k,m}(n+1)-s_{k,m}(n) <\frac1{n(n+1)} $ so that $s_{k,m}(n) < ...