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

Predicates and Indirectly Proving the last step of Mathematical Induction

Okay to illustrate this problem, I'm going to need to give an example, and go through the steps of Mathematical Induction to show where my question is aimed at. Example : Prove that $$ n^2 \geq 2n + ...
7
votes
1answer
104 views

$2005$th derivative of $f$ at $0$

So I tried using Leibnitz formula to solve by recurrence, but I can just get to one point and then it's a mess again. Problem is Let $f(x)=\frac{1}{1+2x+3x^2+\ldots+2005x^{2004}}$. Find ...
1
vote
1answer
54 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
43 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
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
43 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
82 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
0answers
25 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
80 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
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
73 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 ...
1
vote
0answers
181 views

Inequalities of the triangle

I created a inequality below, what you think guys? Let $ \alpha',\beta',\gamma'$ be angles of an acute triangle, and let $ n\in\mathbb{N}^{*}$ and $\displaystyle j\in\mathbb{N}$. Prove that: $$ ...
0
votes
0answers
25 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
86 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
122 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 ...