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
3answers
29 views

Question regarding proving by induction

I am struggling with a math problem I have been assigned. The problem is as follows: Let $X_1 = -3$ and $X_2 = 0$. Given that for every natural number $n \geq 2, X_{n+1} = 7X_n - 10X_{n-1}$, prove by ...
2
votes
0answers
16 views

Partition onto subsets at the same sum

Positive integers $ a_1, a_2,\ldots, a_n $ such that $ a_k\leq k $ and the sum of all these numbers is even and equal to $ 2S $. Prove that the number can be divided into two groups, the amount of ...
0
votes
2answers
48 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 ...
4
votes
8answers
129 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
58 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
36 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 ...
-2
votes
3answers
38 views

Mathematical Induction $\frac{n}{3n+9}$ [on hold]

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}$$
1
vote
3answers
35 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 ...
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
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
37 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
54 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
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 ...
-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 ...
4
votes
5answers
131 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 ...
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 ...
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
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 ...
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
27 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
36 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
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$ ...
-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)$$
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
44 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)}}$ ...
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 ...
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 ...
5
votes
4answers
98 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}$ ...
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)! = ...
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
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
vote
1answer
31 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 ...
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}$$ ...
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 ...
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
18 views

show that $\neg(p_1 \vee p_2 \vee… \vee p_n)$ is equivalent to $\neg p_1 \wedge \neg p_2 \wedge… \wedge \neg p_n$ by induction

Use mathematical induction to show that $\neg(p_1 \vee p_2 \vee... \vee p_n)$ is equivalent to $\neg p_1 \wedge \neg p_2 \wedge... \wedge \neg p_n$ whenever $p_1,p_2,...,p_n$ are propositions. So ...
0
votes
1answer
27 views

Theorem? For every $f:\mathbb{R}\to\mathbb{R}$, for every $A \subseteq R$ where $A$ is finite, $\exists c\in\mathbb{R}:\forall x\in A:(f(x) = c)$.

Your mathematical sense problably twitched when you read the title, as a simple counterexample of the theorem is some one-to-one function. Where then, is the mistake in this proof? Let ...
1
vote
2answers
62 views

Prove by induction $n! > n^2$

I am trying to prove the inequality in the title for $n\geq 4$; however, I am stuck on the induction step! Any help would be appreciated. For $n\ge 4$, prove that $n! > n^2$. Base Case: $n=4$, ...
0
votes
3answers
58 views

Prove that $1 \cdot 1!+2 \cdot 2!+\cdots+n \cdot n!=(n+1)!-1$

Prove that $1 \cdot 1!+2 \cdot 2!+\cdots+n \cdot n!=(n+1)!-1$ whenever $n$ is a positive integer. Basis step: $P(1)$ is true because $1 \cdot 1!=(1+1)!-1$ evaluate to $1$ on both sides. Inductive ...
1
vote
1answer
46 views

Prove by Induction - Sequence

The sequence $x_1, x_2, x_3, \ldots$ is such that $x_1 = 1 $ and $$x_{n+1} \space = \frac{1+4x_n}{5 + 2x_n}$$ Prove by induction that $x_n > 0.5$ for all $n \ge 1$. I have absolutely no clue how ...
5
votes
5answers
182 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.)? ...
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 ...
1
vote
1answer
56 views

Prove summations are equal

Prove that: $$\sum_{r=1}^{p^n} \frac{p^n}{gcd(p^n,r)} = \sum_{k=0}^{2n} (-1)^k p^{2n-k} = p^{2n} - p^ {2n-1} + p^{2n-2} - ... + p^{2n-2n}$$ I'm not exactly sure how to do this unless I can say: ...
0
votes
1answer
33 views

proof some inequality by induction

I got to proof the following in-equality by induction for an assignment but having a hard time. $$ \frac{2n}{(a+b)^n} \leq \frac{1}{a^n} + \frac{1}{b^n} $$ $a,b > 0$ Thanks in adavance!
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 - ...
1
vote
1answer
32 views

Closed Form Summation Example

$$ \sum_{i=1}^n (ai +b) $$ Let $n \geq 1$ be an integer, and let $a,b > 0$ be positive real numbers. Find a closed form for the following expression. In other words you are to eliminate the ...