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

proof by simple mathematical induction question [duplicate]

"Prove using simple induction that for each integer $n \geq 1$, $$ 5 + 5^2 + 5^3 +..... + 5^n = \frac{5^{n+1}-5}4 $$ so I start with base step base step: $n = 1$ $$5^1 = \frac{5^{1+1}-5}4 $$ is ...
0
votes
1answer
32 views

Trying to simplify an expression for an induction proof.

I got it down to $(k+2)!-1 + (k+1)((k+1)!)$ I am trying to get it to $(k+2)!-1$ but I guess I do not understand factorials enough to simplify this. I am also assuming I am doing the induction ...
0
votes
1answer
23 views

Proof through Induction

$\forall n\in\mathbb{N}: n\ge 1 \rightarrow 2^n\le 2^{n+1}-2^{n-1}-1.$ I know the basic part so I won't type it in here, and here is my inductive steps: $2^{k+1}=2^k\cdot 2 \le 2(2^{k+1}-2^{k-1}-1)$ ...
0
votes
6answers
63 views

Prove $4n < n^2 - 7$ for $n$ is greater than or equal to $6$

We are supposed to be proving this by induction and I know the basis is true $4(6) < 36-7$ and the inductive hypothesis is $4n<n^2-7$ for n $ \ge $6 but I am not sure what the next step is. Do I ...
1
vote
1answer
53 views

Truth table and induction

It is true that every truth table can be represented by some wff built using only the connectives $\neg, \implies$ and $\iff$ - let's call it "negation-arrow-wff" for convenience. I want to be able to ...
3
votes
2answers
31 views

Prove that $(()())\in P$ (the set of balanced paranthesis) and $))(() \notin P$

Given the recursive definition of $P$ (the set of balanced paranthesis): Base: $() \in P $. Recursive step: if $w \in P$ then: $$(w) \in P$$ $$()w \in P$$ $$w() \in P$$ And I have to prove that ...
0
votes
2answers
35 views

Strong Induction Explanation

I would like an explanation of the principle of strong induction in general, as well as a formal statement of how to prove a statement true for some subset of integers using it. Specifcally, I am ...
0
votes
1answer
29 views

Mathematical Induction on sports

I have just started with mathematical induction please help me to understand in easy way : There are $n$ players in a match. How do I prove that total number of knockout matches will be $n-1$ to ...
0
votes
2answers
14 views

Need help evaluating the inductive step

I need to evaluate the expression: I have to prove that $7^n-2^n$ is divisible by $5$, for $n \geq 0$; $P(k) \to 7^k - 2^k = 5r$ $P(k+1) \to 7^{k+1} - 2^{k+1}$ I'm starting like this: $7^{k+1} - ...
0
votes
0answers
35 views

Using mathematical induction to prove P(n) [duplicate]

I have the statement $P(n)$: $2^n<(n+1)!$, for $n \geq 2$; $P(2)$: $2^2 < 3!$ which is true I.H P(k): $2^k<(k+1)!$ show that $P(k+1)$: $2^{k+1} <(k+2)!$ Here is my approach: ...
0
votes
2answers
23 views

Induction (Need help with understanding notation)

The image attached below is a problem on induction, the proof has been included. I am enquiring if anyone could explain line for line what the proof states with its notation ( the notation is new to ...
1
vote
5answers
70 views

How to prove that: let $n$ a natural odd, then prove that $x^n<y^n$ iff $x<y$

I tried it in many ways but I couldn't prove it. TASK: Let $n$ a natural odd, $\ \ x,y\in\mathbb{R},$ then prove that $x^n<y^n$ iff $x<y$ My Attempt(s): $$\begin{align} & x^n<y^n \\ ...
1
vote
1answer
19 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
48 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
72 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
26 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
85 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
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
29 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
47 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
61 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
40 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
81 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
123 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
30 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
44 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
27 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
68 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
74 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
27 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
96 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
44 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
36 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
130 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
99 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
44 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
123 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
68 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
57 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. ...