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
18 views

Induction on a Recursive Sequence?

So I don't really know where to go from here, or how to "guess a formula for an" a0, a1,a2... is a sequence that a0 = a1 = 1 and, for n >= 1, an + 1 = n (an +an-1) So I started off by doing the base ...
0
votes
1answer
39 views

Induction Question Is Completely Throwing Me Off

For any $x \in \mathbb{R}$, $x > -1$, $(1 + x) ^ n \geq 1 + nx$ for all $n \in \mathbb{ N }$ I know the steps of induction, (base case, assume, prove), but the was this one is set up is completely ...
1
vote
2answers
26 views

Discrete Math Induction Proof Help With Question

I currently have to do this following proof using induction (base case, inductive hypothesis required) $$\sum_{i=1}^n(6i-3)=3n^2, \forall n>1$$ I'm not really sure how to approach this question ...
0
votes
3answers
42 views

Proof by induction that $1^2 + 3^2 + 5^2 + … + (2n-1)^2 = \frac{n(2n-1)(2n+1))}{3}$

I need to know if I am doing this right. I have to prove that $1^2 + 3^2 + 5^2 + ... + (2n-1)^2 = \frac{n(2n-1)(2n+1))}{3}$ So first I did the base case which would be $1$. $1^2 = ...
2
votes
2answers
71 views

Converging sequence $a_{{n+1}}=6\, \left( a_{{n}}+1 \right) ^{-1}$

I know the sequence is converging. But I find it difficult proving it, by induction. So far I have drawn a diagram and calculate the five first numbers. From the diagram I can se that the sequence can ...
0
votes
1answer
23 views

Prove $|A_1\cup\dotsb\cup A_n|\leq|A_1|+|A_2|+\dotsb+|A_n|$ using Induction

I need help proving Prove $|A_1\cup\dotsb\cup A_n|\leq|A_1|+|A_2|+\dotsb+|A_n|$ (probably using induction. I have already proven that $|A_1\cup A_2|\leq|A_1|+|A_2|$ by $|A_1\cup A_2|= ...
0
votes
1answer
80 views

Why is Mathematical Induction used to prove solvable inequalities?

As a first year undergrad student I've seen problems where solvable inequalities need to be proven to hold in a specific domain using Mathematical Induction. My question is, if the inequalities are ...
-1
votes
1answer
23 views

Proof using mathematical induction

This sum appears to be proved by using mathematical induction. As usual it it's easy for n=1 but i can't prove that for n=k+1. Help me
-1
votes
1answer
41 views

Please help proving a sequence is less than a number using induction [closed]

I need to prove that $$a_n=\left(1+\frac{1}{n}\right)^n <3$$ using induction. Any help would be great!
0
votes
1answer
28 views

Summation of fractions with odd denominators to prove by induction

$$ \frac{1}{1\cdot3}+\frac{1}{3\cdot5}+\dots+\frac{1}{(2n-1)(2n+1)} = \frac{n}{2n+1} $$ As you can imagine I am stuck in third step in $k+1$. Hope you can help. 
2
votes
2answers
29 views

Induction proof that for every convex n-corner there are n(n-3)/2 diagonals

I have to proof that that for every convex n-corner there are $n(n-3)/2$ diagonals. 1.First step is to find n for which the sentence is correct. If $n0 = 3 => n(n-3)/2 = 0$. It is true because ...
0
votes
1answer
28 views

Showing multiplication inequality using induction

Use induction to show that: $$\frac{1}{2}\frac{3}{4}\dots \frac{2n-1}{2n} < \frac{1}{\sqrt{3n+1}} $$ for $n > 1$.
0
votes
2answers
45 views

Induction proof for expression $4^n > n^3$

I'm trying to proof that expression $(4^n>n^3)$ for $n\in \mathbb{N}$ using the induction. 1.There is $n0 = 0 $ for what $L=4^0=1$ and $P=n^0=0$ That is why $L>P$ 2.Let's see what happen ...
1
vote
1answer
28 views

Evaluation of an expression

I have difficulties to evaluate this expression to the desired result. (It is a proof based on mathematical induction, left = right) $(k+1)!-1+(k+1)*(k+1)! = (k+2)!-1$
1
vote
1answer
60 views

Show that $\sqrt{2}$ is an irrational number with strong mathematical induction

Use strong induction to show the following : $$\sqrt2\:\text{is an irrational number}$$ $\\$ $\color{red}{\text{Note}}$ : P$(n)\equiv$ $\sqrt{2}$ $\neq \large\frac{n}{b}\small\text{,}\:$$\forall ...
0
votes
1answer
39 views

Proving infimum

I have to prove: If $x_n=\frac{3n-1}{n},\ x\in\Bbb{R},n \in \Bbb{N}$, then $\displaystyle\inf_{n\in\Bbb{N}}\{x_n\}=3$. First I have to prove by induction the sequence is growing, but then i got ...
-2
votes
1answer
28 views

Help with proof by induction of inequality [duplicate]

I am studying for an exam and going through various earlier tutorial sheet questions. For the question below, I have tried and just can't figure out how to prove that $x$n$ $ < $ 3$ by mathematical ...
0
votes
3answers
77 views

Peano Induction Axiom

This is a typical rendition the Peano Axiom of Induction: If subset $S \subseteq \mathbb{N}$ contains $1$ and is closed under the successor function (i.e., $n \in S$ implies $\sigma\text{n} \in S$ ...
3
votes
4answers
122 views

Using induction, show ${(1+\sqrt{2})}^{2n}+{(1-\sqrt{2})}^{2n}$ is an even integer.

I'm having serious difficulties with that task, so it should be nice, if there is someone that can help! The task says: Prove that the number $${(1+\sqrt{2})}^{2n}+{(1-\sqrt{2})}^{2n}$$ is an ...
0
votes
1answer
31 views

If $f_1, f_2, f_3,\ldots$ is the Fibonacci sequence proof $f_1^2 + f_2^ 2 + \cdots + f_n^2 = f_n f_{n+1}$. [duplicate]

I'm assuming this is using strong induction/ regular induction. However, besides the "base case" I'm really confused with the inductive steps in my notes. The inductive steps in my notes use the ...
0
votes
2answers
29 views

Using only postage stamps of value 64 and 55, how can I work out the way to get closest to a high parcel value?

Searching has shown many questions like this for values of 4 and 7 cents, but nothing for higher values. For British postage, first class stamps are £0.64 and second class are £0.55. Low value stamps ...
0
votes
1answer
38 views

Proof a formula of the Fibonacci sequence with induction

It turns out that the Fibonacci sequence satisfies the following explicit formula: For all integers $F_{n} ≥ 0$, $F_{n} = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n+1} - ...
0
votes
1answer
26 views

Induction proof for the sequences(arithmetic mean and geometric mean)

Let a and b be positive numbers with a > b. Let $a_1$ be their arithmetic mean and $b_1$ their geometric mean: $$ a_1 = \frac{a + b}{2}$$ $$b_1 = \sqrt{a*b} $$ Repeat this process so that, in ...
3
votes
4answers
65 views

Induction for divisibility: $3\mid 12^n -7^n -4^n -1$

I must use mathematical induction to show that $a_{n} = 12^n −7^n −4^n −1$ is divisible by 3 for all positive integers n. Assume true for $n=k$ $a_{k} = 12^k -7^k -4^k -1$ Prove true ...
1
vote
2answers
50 views

Mathematical induction with the Fibonacci sequence [duplicate]

Let $F_n$ be the Fibonacci sequence: $$ F_0 = 0,\ F_1 = 1 \\ F_n = F_{n−1} + F_{n−2}, n \geq 2 $$ Use mathematical induction to prove that for all positive integers $n$, $$\sum_{i=0}^n (-1)^i \cdot ...
0
votes
5answers
72 views

Proof by Induction - How can I get familiar with it?

I'm taking Discrete Structures now and I can't seem to get comfortable with proof by induction. I understand the concept, and the general procedure...but it all just seems like random algebra ...
0
votes
0answers
24 views

Generalized Euler's Formula for number of pieces?

I am trying to generalize Euler's formula ($f+v-e=2$) for multiple pieces (pieces meaning different parts with no edges connecting the parts). I decided to do induction on the number of pieces, base ...
1
vote
3answers
84 views

Using the Principle of Mathematical Induction to Prove propositions

I have three questions regarding using the Principle of Mathematical Induction: Let $P(n)$ be the following proposition: $f(n) = f(n-1) + 1$ for all $n ≥ 1$, where $f(n)$ is the number of subsets ...
0
votes
2answers
43 views

Prove a Recursive Formula by Induction?

So I have a bonus question on a homework assignment I am working on that literally just asks "How would you prove a recursive formula by induction?" There are no numbers, or sequences given. I ...
0
votes
0answers
35 views

Strong induction proof of number of diagonals

So I understand the regular induction proof about the formula to get the number of diagonals of polygon. But I wish to prove it by strong induction. I think the proof I wrote below is a weak ...
0
votes
0answers
25 views

A question about induction

Prove $(a^{-1}ba)^n = a^{-1}b^na$ for all $n \in \mathbb Z$ and $a, b$ in a group. Assume $n \ge 1$. The identity is true for $n = 0, 1.$ Proof for $n + 1: (a^{-1}ba)^n = (a^{-1}ba)^{n + 1} = ...
4
votes
2answers
121 views

What exactly is the 'induction trap'

I've looked everywhere, and I've looked at a lot of examples. I don't quite understand what about the induction trap is so wrong. The most common example is the graph theory tree example (page 5 here: ...
1
vote
1answer
97 views

Show that there are always two teams who played exactly the same number of games.

So i was given this question. There are 11 teams in a league. Each team can play against the other team only once. Show that there are always two teams who played exactly the same number of games. My ...
7
votes
2answers
88 views

Proof by induction, utilizing inductive assumption

Show that for every natural number $n$ there exist integers $x,y$ such that $$4x^2 + 9y^2\equiv 1\pmod{n} $$ The base case is trivial, since 1 divides anything. Assume the claim holds for some ...
1
vote
1answer
42 views

Proof By Induction With Integration Problem

I am required to prove this formula by induction$$ \int x^k e^{\lambda x} = \frac{(-1)^{k+1}k!}{\lambda^{k+1}} + \sum_{i=0}^k \frac{(-1)^i k^\underline{i}}{\lambda^{i+1}}x^{k-i}e^{\lambda x}$$ where ...
3
votes
5answers
112 views

7 Cents and 11 cents Stamps Mathematical Induction

Assume you can only use 7-cent and 11-cent stamps. a) Determine which amounts of postage can be formed by the given stamps. b) Prove your answer using the principle of mathematical induction. c) ...
2
votes
3answers
67 views

Proof using induction n!

I wanna know how to proof using induction; I saw this example in a discrete book; however, i could not solve it; the question is below: Prove, using induction, that $3^{n} < n!$ for all $n ≥ 7$
2
votes
1answer
56 views

Is the sequence a graphic sequence?

Let $S=\{a_1,a_2,\dots,a_n\}$ be a set of distinct integers. Let $k$ is the least common multiple of the numbers $\{a_1+1,\dots,a_n+1\}$. Prove that the sequence that is take all the elements of $S$ ...
0
votes
4answers
52 views

Induction proof: $n^2+3n$ is even for every integer

Prove using simple induction that $n^2+3n$ is even for each integer $n\ge 1$ I have made $P(n)=n^2+3n$ as the equation. Checked for $n=1$ and got $P(1)=4$, so it proves that $P(1)$ is even. ...
0
votes
0answers
18 views

Solving recurrence relation $T(n)\le T(0.9n)+T(0.2n)+O(n)$

I'm trying to solve the following recurrence relation $$T(n)\le T\left(\frac{9}{10}n\right)+T\left(\frac{1}{5}n\right)+\text{O}(n)$$ According to book it should be that $T(n)=\text{O}(n^2)$. I ...
2
votes
1answer
49 views

Valid Induction Argument involving Closed Form for $\Gamma(1/2-n)$

Given $\Gamma\left(\frac1{2}\right)=\sqrt{\pi}$, $$\sqrt{\pi}=\Gamma\left(\frac1{2}\right)=\Gamma\left(-\frac1{2}+1\right)=-\frac{1}{2}\Gamma\left(-\frac1{2}\right)$$ and so ...
2
votes
1answer
42 views

Proof of a Four-Pole Tower of Hanoi

Four-Pole Tower of Hanoi: Suppose that the Tower of Hanoi problem has four poles in a row instead of three. Disks can be transferred one by one from one pole to any other pole, but at no time may a ...
3
votes
1answer
78 views

Proof with induction for a Tower of Hanoi with Adjacency Requirement

Tower of Hanoi with Adjacency Requirement: Suppose that in addition to the requirement that they never move a larger disk on top of a smaller one, the person who move the disks of the Tower of Hanoi ...
1
vote
3answers
88 views

Divisibility by 4 (induction proof)

We have to show that $$ n^4 -n^2 $$ is divisible by 3 and 4 by mathematical induction Proving the first case is easy however I do not know how what to do in the inductive step. Thank you.
1
vote
0answers
53 views

Induction in the Reals?

In most maths textbooks, proofs by induction prove a statement $P_n$ where $n$ usually is in the natural numbers (although I understand that it can be in any discrete collection as long as you prove ...
-1
votes
1answer
57 views

Mathematical Induction in constructive setting [closed]

I'm little confused. As we don't have a proof hence we can't say : let the equation holds till(for) fixed n, and then we are going to show (prove) it holds for n + 1. From this argument mathematical ...
1
vote
2answers
49 views

Im having trouble with a proof by induction

the question is: let $$a_{n} = 1$$ and $$a_{n+1}=\frac{a_{n}}{1+(n+1)a_{n}}$$ for each natural number n. prove by induction that $$a_{n} = \frac{2}{n(n+1)}$$ for every natural number. and deduce that ...
1
vote
1answer
26 views

Prove that every permutation in $S_k$ is the product of transpositions of the form $(j, j + 1).$

Prove that every permutation in $S_k$ is the product of transpositions of the form $(j, j + 1).$ I proved the case $n=2$ for my base case... so $(12)=(21)$ and $(21)=(12)(12)$ then I proved $n=3$ and ...
1
vote
1answer
40 views

Show that $H_{2^n}$ $\leq$ $1+n$ with induction

Use mathematical induction to show that $H_{2^n}$ $\leq$ $1+n$, whenever n is a nonnegative integer. PS: $H_{2^n}$ denotes the $2^n$th harmonic number.
2
votes
1answer
54 views

Prove Dirac's Theorem by induction on the number of vertices

Dirac's Theorem says: If a connected graph $G$ has $n \ge 3$ vertices and $\delta(G) \ge \frac{n}{2}$, then $G$ is Hamiltonian. Now I want to prove this theorem by induction on $n$. For ...