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
8answers
106 views

Proving that $5^n-1$ is divisible by $4$ for $n\geq 0$ by induction

I hope this is not counted as a duplicate, as I would like to know if my proof is valid: $P(n): 5^n - 1$ is divisible by $4$ for $n \ge 0$. Base Step: $P(0): 5^0-1 = 1-1 = 0 = 0\times 4$. Induction ...
0
votes
2answers
42 views

Using induction to prove letter arrangement

There are n letters written to different people, and envelopes correspondingly addressed. The letters are mixed before being sealed in envelops, the effect being to make n!allocations of letters to ...
0
votes
2answers
50 views

What are the prerequisites required if I have to do induction to prove a certain theorem

I have always been fascinated by induction. The idea of induction is itself such a great analogy. But sometimes induction makes me feel that it is very messy. My professor keeps on saying that you ...
0
votes
4answers
33 views

Show that the sequence is monotone and bounded.

Show that the sequence defined by $a_1=1$ and $a_n=\sqrt{3+a_{n-1}}$ for $n>1$ is monotone and bounded. Then find the limit of the sequence. I'm supposed to do this using induction. I'm usually ...
1
vote
3answers
31 views

How to prove a Fibonacci inequality using Strong Induction?

Using strong induction I am trying to prove that $$F_n \geq \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} \text{ for all } n \geq 2$$ for the Fibonacci Sequence defined by: $F_0 = 0$, $F_1 = 1$, and $F_n ...
-2
votes
3answers
36 views

Mathematical Induction $\frac{n}{3n+9}$

Use mathematical induction to prove that for every positive integer $n$, $$\dfrac{1}{3\cdot 4} + \dfrac{1}{4\cdot 5} + \ldots + \dfrac{1}{(n+2)(n+3)} = \dfrac{n}{3n+9}$$
3
votes
1answer
788 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
1
vote
1answer
32 views

Induction Clarification

I had this problem: Is it always necessary to go from n to (n + 1) or from (n - 1) to n in the inductive hypothesis? Is the "direction" always important? Here is my solution to one such proof, which ...
1
vote
1answer
91 views

How do I prove $F_{n+1}^2 - F_nF_{n+2} = (-1)^n$ using induction? [duplicate]

$F_n$ refers to the $n$ term of the Fibonacci Sequence. I think I'm supposed to prove this by induction. I already have the base case. I am at: $\text{F}_\text{k+1}^2 - F_k\text{F}_\text{k+2} + ...
1
vote
2answers
64 views

Proving $n^2≤2^n+1$ for $n\geq 1$ by induction

Prove $n^2\leq 2^n+1$ for $n\geq 1$ using induction. Proof. For $n=1, (1)^2\leq 2^1+1=3$. $\therefore 1\leq 3$ is true. Assume $n=k$ is true so $k^2\leq 2^k+1$ or $k^2-1\leq 2^k$. Then prove for ...
1
vote
2answers
50 views

How to prove that the statement $ 4+10+16 + \cdots + (6n-2) = n(3n+1)$ for all $n \ge 1$ using mathematical induction?

I know you begin by establishing that it is true for $n=1$ which gives $6(1)-2 = 1(3\cdot1\cdot+1)$. Then I replace each $n$ for a $k$, and I suppose that is true for $6k-2=k(3k+1)$. But then the ...
-2
votes
0answers
31 views

Prove by induciton that the Merge(A,B) algorithm is correct

I am asked to prove the correctness of the Merge(A,B) algorithm that merges two arrays A and B into an array C. Merge(A,B) Algorithm: a) Given two lists A and B b) If A is the empty list then ...
1
vote
0answers
32 views

Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
3
votes
2answers
52 views

Solve the following recurrence relation: $S(1) = 2$; $S(n) = 2S(n-1)+n2^n, n \ge 2$

Solve the following recurrence relation: $$\begin{align} S(1) &= 2 \\ S(n) &= 2S(n-1) + n 2^n, n \ge 2 \end{align}$$ I tried expanding the relation, but could not figure out what the closed ...
1
vote
2answers
63 views

Confusion about how to prove $\sum_{i=0}^n 2^i = 2^{n+1}-1$ for all $n\geq 0$ by induction

I'm trying to understanding proof by induction. But how do I check if that is correct? How do I know what I need to show? Any help would be great. Just trying to get my head around this. So I have ...
1
vote
1answer
41 views

Lucas Number Sequence

Can anyone help me in this question: Define $ (b_n)$ as $b_1= 1,b_n=a_{n+1} - a_n $ for $ n\ge 2$, where $ a_n $ is the Fibonnaci series. This sequence is known as the sequence of Lucas numbers. ...
1
vote
1answer
30 views

Proving the principle of definition by generalized recursion using the inductive closure of an induction system

I'm working through Hinman's Fundamentals of Mathematical Logic in order to review some things, and got stuck in an exercise from section 1.2. Specifically, he asks us to prove (what he calls) the ...
1
vote
3answers
71 views

Show that the sequence defined recursively by $a_{n+1} = \sqrt{3a_n + 1}$ is increasing

Assume that the sequence ${a_n}$ is defined recursively by $a_{n+1} = \sqrt{3a_n + 1}$ for all $n \in \mathbb N$, with $a_1 = 1$. Use mathematical induction to prove that $a_n \leq a_{n+1}$ for all ...
4
votes
5answers
128 views

Inequality in Algebra: $1 \leq x_1 x_2 \cdots x_n$ implies that $2^{n} \leq (1 + x_1)(1+x_2) \cdots (1 + x_n).$

How do I prove that if $x_1, \ldots, x_n$ are positive real numbers, then $$1 \leq x_1 x_2 \cdots x_n \text{ implies that } 2^{n} \leq (1 + x_1)(1+x_2) \cdots (1 + x_n).$$ I attempted a proof by ...
0
votes
2answers
36 views

Strong Induction

Define a recursive sequence $a_0$, $a_1$, $a_2$, . . . by $a_0 =1$,$a_1 =3$, $a_n$ = $2a_{n−1}$ + $8a_{n−2}$ for all integers $n≥2$ Prove by strong induction that $a_n$ $≤ 4^n$ for all integers $n ≥ ...
1
vote
1answer
30 views

Proving Inequality using Induction.

I am trying to prove the following statement: For every nonnegative integer $n$, $1+6n \le 7^n$. I did the base case where $n=0$ but am having trouble manipulating the inductive step. So far I ...
1
vote
2answers
26 views

How do I prove this with induction?

I am give $a_{n+1}=\sqrt{a_{n}+12}$ and $a_{n}∈[-12, 4]$. I need to prove $0≤a_{n}≤4$ for all $n≥2$. I have that $a_{2}∈[0,4]$ so it works for the first case and $a_{3}∈[\sqrt{12},4]$ so it holds for ...
0
votes
0answers
35 views

Solving a general system of linear equations

We are given a system with n linear equation: $$\forall i\in \{1,...,n\}: i \cdot x_i + \sum_{j=i+1}^{n}x_j= \frac{i}{n}$$ Prove that the solution for this system of equation is $$\forall i\in ...
2
votes
1answer
49 views

Induction Proof on String

Formally prove the correctness of the union construction as follows. Let $M_1$ and $M_2$ be the two $\lambda$-NFA's constructed for $R_1$ and $R_2$ and let $N$ be the $\lambda$-NFA constructed so ...
-1
votes
3answers
88 views

Use mathematical induction to prove a statement [on hold]

Use mathematical induction to prove that: $$A\cap\left(\bigcup_{i=1}^nB_i\right) = \bigcup_{i=1}^n\left(A\cap B_i\right)$$
1
vote
2answers
51 views

How can I prove using induction that the Hadamard matrices are orthogonal?

I can't figure out how to prove using induction that the dot product of 2 rows in a Hadamard matrix is 0. I've always thought of it as just a property of the type of matrix.
2
votes
1answer
31 views

Understanding an application of induction in a proof

I understand what is done below, however I don't understand the induction used, especially not when applying $0\leq n$. If $s_n+1=f(s_n)$ with $|f′(x)|\leq 1/2$ prove that the sequence $s_n$ ...
2
votes
2answers
24 views

Help with Factorial Inequality Induction proof

So I'm asked to prove $3^n + n! \le (n+3)!$, $\forall \ n \in \mathbb N$ by induction. However I'm getting stuck in the induction step. What I have is: (n=1) $3^{(1)} + (1)! = 4$ and $((1) + 3)! = ...
0
votes
2answers
23 views

Help with solving mathematical induction problem

I need help with the following: Use mathematical induction to prove that for every $n\in N$, $$ \sum_{k=1}^n\frac{1}{\cos kx \cos(k+1)x}=\frac{\tan(n+1)x-\tan x}{\sin x} $$ For $n=1$, the statement ...
0
votes
2answers
59 views

Prove for integers $a,b\ge 3$ that $a^2+b^2+1>(a+1)(b+1)$

Prove for integers $a,b\ge 3$ that $a^2+b^2+1>(a+1)(b+1)$. Original question asked for positive real solutions, but I've changed it to integers. It's question I've come up with. AM-GM ...
2
votes
3answers
43 views

Can mathematical inductions work for other sets?

I know that induction works only for the natural numbers $\mathbb{N}$. We first have to prove the base case. And we then prove that if the statement $p(k)$ holds then $\color{blue}{\textbf{p(k+1)}}$ ...
4
votes
3answers
84 views

Inductive Proof that $k!<k^k$, for $k\geq 2$.

Call $P(k): k!<k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2<4$). Assume that $P(k)$ is true for some $k\geq2$. Then show that $P(k+1)$ is true. $P(k+1): (k+1)!<(k+1)^{k+1}$ ...
3
votes
2answers
48 views

Proof By Contradiction [?]

There are $n$ islands with $n$ bridges connecting pairs of islands (where $n\ge 2$). Prove that some sequence of distinct bridges forms a loop. __ Since it isn't obvious how to prove it directly I ...
3
votes
7answers
157 views

Hint in Proving that $n^2\le n!$ [duplicate]

The problem is to find the values of n such $n^2\le n!$. I have found this set to be {${n\in Z^+| n\le1 \lor n\ge 4}$} I've used a proof by cases to prove the first part ($\forall n\le 1$) which was ...
2
votes
3answers
191 views

How to prove a sum of series

How do I prove that for any natural number $n$ we have $$\sum_{i=0}^n i^4 \neq \left(\sum_{i=0}^n i\right)^3?$$ Any help would be greatly appreciated.
-1
votes
1answer
25 views

Help with a demonstration with triangle numbers

Recently I've been doing some work with trianglular numbers. Basically I wanted to show that for every nth triangular number $T_n$ $$T_n=\frac{n(n+1)}2$$ For me the simplicity if this equation is ...
3
votes
3answers
113 views

Proof verification for proving $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ by induction

Prove by mathematical induction: $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ Basis Step: (We want to show, $P(2)$, which is 1 + ...
1
vote
3answers
47 views

Simple Induction Proof

How would one go about proving that $$0<\frac{n}{n+1}<1$$ by mathematical induction? If $p(n)$ is the statement as above, then I know we show $p(1)$, and assume $p(n)$, but in this particular ...
2
votes
3answers
490 views

Summation and proof by induction question: $\sum_{j=1}^{n}j(j+1)(j+2)=\frac{n(n+1)(n+2)(n+3)}{4}$

I can't figure this out based on examples in textbooks, etc. Show via induction that $\sum_{j=1}^{n}j(j+1)(j+2)=\frac{n(n+1)(n+2)(n+3)}{4}$ So far, I have: (a) base case $P(1)= 1(1+1)(1+2) = ...
1
vote
2answers
70 views

Inductive proof and summation: $\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$

The problem asks me to prove by induction that: $$\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$$ I've worked through it at least half a dozen times, checked my math fastidiously, can't seem to figure it ...
0
votes
3answers
45 views

Induction summation proof: $\sum_{i=1}^{n} \frac{4}{5^{i}} < 1$

Don't want a full answer but can somebody help me in the right direction with this problem. Have to prove using induction $$\forall n \geqslant 2: \sum_{i=1}^{n} \frac{4}{5^{i}} < 1$$
20
votes
3answers
581 views

A (probably trivial) Induction Problem: $\sum_2^nk^{-2}\lt1$

So I'm a bit stuck on the following problem I'm attempting. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling with some ...
2
votes
2answers
30 views

Use induction to figure out the number of handshakes in a party

Every arriving guest shakes hand with everybody else at a party. If there are n guests in the party, how many handshakes were there? Proof by using induction. My approach to this problem was to write ...
12
votes
2answers
718 views

Inverted induction

I am working on a proof, and to do it, I think it would be optimally to use induction backwards. Show that 1 doesn't work. Assume n doesn't work. Prove that n+1 doesn't work. Is this valid?
3
votes
3answers
40 views

Proving that $8^n-2^n$ is a multiple of $6$ for all $n\geq 0$ by induction

I have the following induction problem: $8^n-2^n$ is a multiple of $6$ for all integers $n\geq 0$. So far this is what I've done: Base case: $n = 0$ $8^0-2^0 = 6$ $1 - 1 = 6$ $0 = 6$ This ...
5
votes
5answers
179 views

Proof writing: how to write a clear induction proof?

What is an effective way to write induction proofs? Essentially, are there any good examples or templates of induction proofs that may be helpful (for beginners, non-English-native students, etc.)? ...
5
votes
1answer
68 views

Proving $\frac {2n}{(a+b)^n} \le \frac {1}{a^n} + \frac {1}{b^n}$ for $a,b>0, n\in\mathbb{N}$ by induction

prove using induction: $$ \frac {2n}{(a+b)^n} \le \frac {1}{a^n} + \frac {1}{b^n} $$ $$a,b \gt 0 , n \in N$$ my attempt: base $n=1$: $$ \frac {2}{(a+b)} \le \frac {1}{a} + \frac {1}{b}$$ ...
0
votes
0answers
22 views

Relationship between inductive reasoning and first order reasoning [closed]

I know what is induction and tableau reasoning. I happen to see that if reasoning is done via induction, then the reasoning is not first order. Why inductive reasoning and first order reasoning are ...
2
votes
4answers
113 views

Prove that $371\cdots 1$ is not prime.

Prove that $371\cdots 1$ is not prime. I tried mathematical induction in order to prove this, but I am stuck. My partial answer: To be proved is that $37\underbrace{111\cdots 1}_{n\text{ ...
2
votes
1answer
60 views

“Cascade induction”?

I refer to this answer. The answer is based on several simplification steps, all of them proven by induction. $S_n = 2903^n - 803^n - 464^n + 261^n$ $T_n = 2642\cdot2903^n - 542\cdot803^n - ...