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
4answers
42 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
65 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
36 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
59 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
54 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
68 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
68 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 ...
4
votes
5answers
143 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
71 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
41 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
82 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
36 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
29 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
39 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
32 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
98 views

Use mathematical induction to prove a statement [closed]

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
26 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
70 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
53 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)}}$ ...
0
votes
2answers
57 views

Prove by induction that for a natural number a there exists integers $x, y$ where $a = 7x + 2y?$

I am trying to get my head around induction at the moment and found this problem in a textbook. I think that I should be doing induction on $a$, but I can't even see where to start the proof.
3
votes
2answers
50 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
198 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.
0
votes
1answer
29 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 ...
6
votes
4answers
111 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
31 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
116 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
50 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 ...
2
votes
1answer
43 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
69 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
42 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 ...
3
votes
4answers
141 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{ ...
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
67 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
53 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 ...
6
votes
5answers
246 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
31 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
57 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
35 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
61 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
38 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 ...
2
votes
1answer
52 views

Proof By Induction - $n^2 = \sum_{i=1} ^{n} (2i-1)$ for all $n\geq 1$ [duplicate]

Using Proof By Induction I am trying to prove the following: $n^2 = \sum_{i=1} ^{n} (2i-1) $ for all $n\geq 1$ Here is my solutions so Far: Base Case: $n=1, LHS: 2(1)-1 = 1, RHS = 1^2 = 1, True$ ...
8
votes
4answers
193 views

Proving that $\frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{2n}>\frac{13}{24}$ by induction. Where am I going wrong?

I have to prove that $$\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{2n}>\frac{13}{24}$$ for every positive integer $n$. After I check the special cases $n=1,2$, I have to prove that the given ...
1
vote
0answers
20 views

Show that $f(b^i n) \le c^i f(n)$

Let $f$ be a b-smooth function. Let $c$ and $n_0$ be constants such that $f(b n) \le c f(n)$ $\forall $ $n \ge n_0$. Show that $\forall $ $ i \in \mathbb{N}, f(b^i n) \le c^i f(n)$ I thought I should ...
2
votes
3answers
47 views

$\sum_{k = 1}^{n} \frac{1}{k^{2}} < 2 - \frac{1}{n}$ [duplicate]

Prove that for $n\geq 2, \: \sum_{k = 1}^{n} \frac{1}{k^{2}} < 2 - \frac{1}{n} $ I used induction and I compared the LHS and the RHS but i'm getting an incorrect inequality
0
votes
1answer
28 views

Induction Mathematics and Factorials

\usepackage{amsmath} Evaluate the sum $\sum_{k=1}^{n} {k\over (k+1)!}$ $\sum_{k=1}^{1} {1\over (1+1)!} = {1\over 2}$ $\sum_{k=1}^{2} {2\over (2+1)!} = {5\over 6}$ $\sum_{k=1}^{3} {3\over (3+1)!} ...
0
votes
2answers
40 views

Proving 9 divides a cubic by Induction

I have just started to cover induction mathematics in my Discrete Mathematics class and I'm a little confused as to where to go with this problem. Am I on the right track? Prove that 9 divides (n^3 ...
4
votes
2answers
48 views

Proving that $F_{kn}$ is a multiple of $F_n$ by induction on $n$ (Fibonacci numbers)

Question: I want to prove that $F_{kn}$ is a multiple of $F_n$. Approach: I have to deduce this result from the following results: $$F_{n+k} = F_{k}F_{n+1} + F_{k-1}F_{n}$$ I have shown the ...
3
votes
2answers
40 views

Proving $1+5+9+\cdots+(4n+1) = (n+1)(2n+1)$ by induction (is there a typo?)

Using mathematical induction, prove that $$1+5+9+\cdots+(4n+1) = (n+1)(2n+1).$$ I understand the steps to take in order to prove by induction. It is also to my understanding that step 1 would be ...