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

0
votes
0answers
32 views

How to induct for double summation?

I have no idea on how to approach this? $$ \sum_{i=1}^{n}\sum_{j=1}^{m}a_i + a_j = \sum_{i=1}^{n} a_i + \sum_{i=1}^{m} a_j (it \space may \space be \space wrong \space it \space is \space just ...
0
votes
3answers
69 views

Prove by induction that the Fibonacci sequence $≤ [(1+\sqrt{5})/2]^{n−1}$, for all $n ≥ 0$.

If $F(n)$ is the Fibonacci Sequence, defined in the following way: $$ F(0)=0 \\ F(1)=1 \\ F(n)=F(n-1)+F(n-2) $$ I need to prove the following by induction: $$F(n) \leq \bigg(\frac{1+\sqrt{5}}{2}\...
0
votes
1answer
39 views

Find a recurrence for the number of ways to arrange cars in a row with $n$ parking spaces

Find a recurrence for the number of ways to arrange cars in a row with $n$ parking spaces if we can use Cadillacs or Hummers or Fords. A Hummer requires two spaces, while a Cadillac or Ford requires ...
0
votes
3answers
38 views

Induction mathematics

Assume $a_1 = 4$ and $a_{n+1} = \sqrt{3+2a_n}$ for all integers $n ≥ 1$. Show with induction that $\forall n ≥ 1, \space a_n > a_{n+1} > 3$. Help me solve this please
2
votes
2answers
29 views

Sum of reciprocals of squares - bounding

Recently in class our teacher told us about the evaluating of the sum of reciprocals of squares, that is $\sum_{n=1}^{\infty}\frac{1}{n^2}$. We began with proving that $\sum_{n=1}^{\infty}\frac{1}{n^2}...
1
vote
5answers
86 views

Proving that $8^n - 3^n$ is divisible by $5$

I really should be able to do this but I don't know why I can't figure it out. My problem is that I have to prove $8^n - 3^n$ is divisible by $5$. So what I did is I tried it for $n=1, n=2, n=3$ and ...
1
vote
2answers
42 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
105 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 $f^{[2005]}...
1
vote
1answer
62 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
64 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
54 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} - 2^...
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: $2^k<(...
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
71 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
20 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
41 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
52 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 = (1(2(1)-1)(2(1)+1)...
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
27 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|= (|A_1|+|A_2|...
0
votes
1answer
91 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
29 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
36 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
48 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
65 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 b\...
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
29 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
85 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
33 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} - (\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
69 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
51 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
75 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
32 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
101 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
45 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 induction....
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} = (a^{-1}...