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
1answer
30 views

Proving merge sort is $O(n^2)$ using induction

I'm trying to show that merge sort is $O(n^2)$ using induction. (I'm just concerned with powers of two for simplicity). However, I'm stuck at the last inequality Basis step: Show that there exists a ...
1
vote
0answers
43 views

Induction proof: $\det(M) = \prod_{1 \le j \le n} (x_j - x_i)$

Following problem: Let $\mathbb{K}$ be a Field and $M = \begin{pmatrix} 1 & x_1 & \ldots & x_1^{n-1} \\ \vdots & \vdots & & \vdots \\ 1 & x_n & ...
3
votes
2answers
59 views

Matrix problem with inductive solution

Yesterday I was at an interview and was given the following problem: Consider a matrix A that has dimensions NxM. Every element of the matrix is the average of its adjacent (up to 8) elements. Given ...
3
votes
1answer
32 views

How to prove inequality from $n-1$ to $n$ using induction?

My question concerns on the one hand a specific inequality and on the other hand a general strategy on how to approach inequalities in general. Usually I don't have problems using induction in ...
1
vote
3answers
65 views

Proving $ 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ for all $n\geq 2$ by induction

Question: Let $P(n)$ be the statement that $1+\dfrac{1}{4}+\dfrac{1}{9}+\cdots +\dfrac{1}{n^2} <2- \dfrac{1}{n}$. Prove by mathematical induction. Use $P(2)$ for base case. Attempt at ...
1
vote
4answers
62 views

Prove $(2n + 1) + (2n + 3) + \cdots + (4n - 1) = 3n^2$ by induction

This might be an easy problem for you, but I am having difficulties in understanding the formula. As we can see, we have a pattern $$2n + \text{odd number}$$ in $$(2n + 1) + (2n + 3) + \cdots + ...
1
vote
1answer
41 views

Proof by Strong Induction

$a_0 = 1, a_1 = 1, a_k = 2a_{k-1} + 2a_{k_2}$ for $k≥2$ For all integers $n≥0$, $a_n= \frac{1}2[3^{n}+(-1)^n$] Proof By Strong Induction: Basis: $F(0), F(1), F(2), F(3), F(4), F(5)$ Inductive ...
4
votes
3answers
47 views

Proof by Strong Induction for $a_k = 2~a_{k-1} + 3~a_{k-2}$

$$\begin{align} a_0 &= 1 \\ a_1 &= 1 \\ a_k &= 2~a_{k-1} + 3~a_{k-2} \quad \text{ for } k \ge 2 \end{align}$$ Proof by Strong Induction: For all non-negative integers $n$, $a_n$ is an ...
2
votes
2answers
90 views

Proving $2^{2^n}+3^{2^n}+5^{2^n}$ is divisible by $19$ for all $n\geq 1$ by induction

I came across the following in the book Handbook of Mathematical Induction: $$ 19\mid (2^{2^n}+3^{2^n}+5^{2^n}),\quad n\in\mathbb{Z^+}\tag{1} $$ Apparently, this problem is not so bad if you think ...
1
vote
3answers
47 views

Prove by induction $n^2 \leq n!$ for $n\geq 4$.

I managed to get $P(4):4^2 = 16 \geq 24 = 4!$ But then assuming $n^2 \geq n!, \forall n\geq4\in\mathbb{Z}$, I need to prove $(n+1)^2 \geq (n+1)!$ I tried $n^2+2n+1\geq n!\cdot (n+1)$, but I got ...
1
vote
1answer
52 views

is it possible to use induction to prove the following?

I know for sure that there is some easy way to prove what I am about to tell, but, at first, I'd like to know if I can set up a proof by induction for two "cross-referenced formulas". I have two ...
1
vote
1answer
41 views

Use the principle of mathematical induction to prove that $n \lt (\frac{3}{2})^n$ for all integers $n \ge 1$.

Here's the problem: Use the principle of mathematical induction to prove that $n \lt (\frac{3}{2})^n$ for all integers $n \ge 1$. Here's what I've got: Base Case: $1 \lt (\frac{3}{2})^1$ is true. ...
0
votes
2answers
55 views

A question on the proof of commutativity of the sum of natural numbers?

I made this question yesterday and today I've been thinking about another aspect of it. But this question is totally related to the previous one: I am trying to make a clarification about a proof of ...
0
votes
2answers
28 views

Binomial coeficient and induction

I tried to do this exercise from a guide of my gf, but I couldn't. The exercise is: $$\sum_{i=0}^{n}\binom{n}{i}^{2} = \frac{(2n)!}{n!n!} $$ If anyone can help me, I would really appreciate it! I ...
3
votes
1answer
73 views

Proof by induction: For all $n \geq 1$; $1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} - \cdots +(-1)^{n+1} \frac{1}{n} \leq 1$

Proof by induction: For all $n \geq 1$; $1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} - \cdots +(-1)^{n+1} \frac{1}{n} \leq 1$ This is what I have so far: Base case: for $n = 1$ ...
0
votes
3answers
69 views

Prove that $Z(S_n) = \{(1)\}$ for every $n \geq 3$. Induction

I wonder if this questions can be done by induction. $S_3 = \{(1),(12),(13),(23),(123),(132)\}$ $Z(S_3)$ contains all the elements in $S_3$ that commutes with all the element in $S_3$ We can easily ...
1
vote
1answer
38 views

Proof by induction: Show that for every real number $x\geqslant -1$ and every positive integer $n$, $ (1+x)^n \geqslant 1+nx$

Show that for every real number $x\geqslant -1$ and every positive integer $n$, $(1+x)^n \geqslant 1+nx$. This is what i have so far ...
0
votes
2answers
48 views

Multidimensional Proof by Induction

I have been given a recursive relation $$f(m,n)=f(m−1,n)+f(m,n−1)$$ in which I need to prove by mathematical induction that, $$f(m, n) = {(m + n)!\over(m!n!)}$$ over all natural numbers where $$f(0, ...
5
votes
3answers
54 views

Proving $\sum\limits_{k=1}^{2n} {(-1)^k \cdot k^2}=(2n+1)\cdot n$ for all $n\geq 1$ by induction

How prove the following equality: $a_n$:=$\sum\limits_{k=1}^{2n} {(-1)^k \cdot k^2}=(2n+1)\cdot n$ $1$.presumption: $(-1)^1 \cdot 1^2+(-1)^2\cdot2^2=(2 \cdot 1+1) \cdot 1=3$ that seems legit ...
1
vote
2answers
107 views

Proof that a recursively defined sequence is monotonically decreasing.

I am wanting to prove that the following recursive sequence is monotonic decreasing via proof by induction. Let $ S_1 = 1, ~ S_{n+1} = \frac{n}{n+1} (S_n)^2;~ n \geq 1. $ Here is what I have so far ...
3
votes
4answers
123 views

Are there two meanings to induction?

I've seen mathematical induction in two forms. First form: It seems that if $P(0)$ holds and $\displaystyle ...
3
votes
5answers
66 views

Proving $(n+1)!>2^{n+3}$ for all $n\geq 5$ by induction

I am stuck writing the body a PMI I have been working on for quite some time. Theorem: $∀n∈N ≥ X$, $(n+1)!>2^{n+3}$ I will first verify that the hypothesis is true for at least one value of ...
3
votes
1answer
43 views

Is it possible to extend well ordering principle/induction to all well ordered sets?

Today I was thinking about well ordering of naturals,and how by induction we can prove some properties of natural numbers.Now I started wondering if this is property of natural numbers,which are well ...
0
votes
0answers
23 views

Finding a closed form for $\sum_{k=1}^n \sin(k)$ [duplicate]

I'm trying to prove by induction that $$\sin1+\cdots+\sin(n)=\frac{\sin\left(\frac{n+1}{2}\right)\sin\frac{n}{2}}{\sin\frac{1}{2}}$$ My only thought so far is to use the identity $\sin x+\sin ...
0
votes
3answers
67 views

Difficult induction problem

Been trying to figure this one out for a couple of days to no avail. Appreciate if someone could set me in the right direction. Prove by induction that ...
0
votes
1answer
44 views

Is Proof By Induction Necessary? [duplicate]

Are there any theorems that can only be proved by induction? Induction seems to be proof by technicality.
-1
votes
3answers
64 views

Proof by induction: $\log n < n$ for $n ≥ 1$.

I was just wondering it is possible to prove this statement via mathematical induction? (I know you can do it via calculus but I want to specifically do it via induction). I have given it a go but am ...
2
votes
4answers
67 views

Prove $24\mid5^{2n}+12n^2-36n-1$ using induction

Prove $24\mid5^{2n}+12n^2-36n-1$ using induction What I thought: Inductive hipothesis: $$ 5^{2n}+12n^2-36n-1=24k $$ Inductive step: $$ 5^{2(n+1)}+12(n+1)^2-36(n+1)-1=24q $$ $k,q \in \mathbb{Z}$ ...
1
vote
1answer
50 views

Proof by Induction: Puzzle Pieces Problem

There's a thought puzzle I am struggling to understand that deals with the fundamentals of writing a proof involving the inductive assumption. A jigsaw puzzle is solved by putting its pieces ...
1
vote
3answers
45 views

Mathematical Induction Proof Question dealing with integers

How would you use mathematical induction to prove that $1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + \dots + n \cdot (n + 1) \cdot (n + 2) = \frac{n(n + 1)(n + 2)(n + 3)}{4}$ I tried proving the base ...
-5
votes
1answer
76 views

Estimating partial sums $\sum_{n = 1}^m \frac{1}{\sqrt{n}}$

Apostol's Calculus, exercise number I 4.7 13. Prove that if $n \geq 1$, then $$ 2(\sqrt{n+1} - \sqrt{n}) < \frac{1}{\sqrt{n}} < 2(\sqrt{n} - \sqrt{n-1}) $$ and use this to prove that if ...
2
votes
2answers
42 views

Induction question with 'if' statement

I have an induction homework question that I got stuck in the middle. Prove by induction that if $a + a^{-1} \in \Bbb{Z}$ then for each $n \in \Bbb{N}$ the following is true: $$a^{n} + a^{-n} \in ...
0
votes
1answer
43 views

Proving an operation is closed under regular languages

Following operation is defined over languages where $n \in \mathbb{N} :$ $L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$ Meaning that $L ...
4
votes
3answers
67 views

induction to prove $n^2 - 1$ is divisible by 4 by changing variables

I have to prove $n^2 - 1$ is divisible by $4$, where $n\in\mathbb{O}_{>0}$. It says, "You cannot prove this by induction on $n$. Rewrite $n^2 - 1$ in terms of a variable on which you can do ...
3
votes
4answers
381 views

Is induction valid when starting at a negative number as a base case?

I'm reading the text Discrete and Combinatorial Mathematics by Grimaldi, and he puts forth the theorem of the principle of mathematical induction as such: Let $S(n)$ denote an open mathematical ...
2
votes
1answer
70 views

Prove by induction that numbers of Fibonacci of the form $F_{3n}$ are even

I am not quite asking to solve this problem, but I am asking what they are asking me. This is the problem: The Fibonacci numbers $F_n$ for $n \in \mathbb{N}$ are defined by $F_0 = 0$, $F_1 = 1$, ...
3
votes
2answers
131 views

Inequality and Induction

I needed to prove that $\prod_{i=1}^n\frac{2i-1}{2i}$ $<$ $\frac{1}{\sqrt{2n+1}}$, $\forall n \geq 1$ . I've atempted by induction. I proved the case for $n=1$ and assumed it holds ...
0
votes
2answers
53 views

Using induction to prove a sequence is always less than a given number

Let $f(1)=2$ and $f(n+1)=\sqrt{3+f(n)}$. Prove that $f(n)<2.4$ for all $n\ge 1$. I established a base case when $n=1$ and then moved on to the inductive step by assuming the statement is true ...
1
vote
0answers
19 views

Recurence with multiple variables and functions

Is there an easy way to solve a recurrence given with two variables and three different functions? Actually I'm looking for the solution of: $$A(n,k)=A(n-2,k-1)+A(n-3,k-1)+R(n-2,k-1)+L(n-2,k-1) $$ ...
0
votes
3answers
65 views

Fibonacci induction proof?

The Fibonacci Numbers $(f_n)$ are defined $f_1=f_2=1$, and $f_n=f_{n-1}+f_{n-2} ,\,\,\,\forall n \geq2$. Prove that for every integer $n \geq 1$, $$f_1 +f_2 +···+f_n =f_{n+2}−1$$
0
votes
1answer
28 views

Induction solution for game of coins

Consider a game in which, initially, there is a pile of n coins placed on a table. There are two players who alternate turns. Each player, on her or his turn, removes either one, two, or three coins ...
1
vote
3answers
69 views

Proving $2^n\leq 2^{n+1}-2^{n-1}-1$ for all $n\geq 1$ by induction

I am trying to prove that for every element of $\mathbb{N}$, that $2^n \leq 2^{n+1} - 2^{n-1} - 1.$ I started by showing that initial case, of $n=1$, is true. Then I proceed to the ...
0
votes
2answers
41 views

How to proof $f_{n+1}(x) = x f_n(x) - f_{n-1} (x),\quad n \geqslant 1$ by induction?

Let $$ f_n (x) = \det \begin{bmatrix} x & 1 & 0 & \cdots & 0 \\ 1 & x & 1 & 0 & 0 \\ 0 & 1 & x & 1 & \vdots \\ \vdots & & & \ddots & 1 ...
0
votes
1answer
24 views

How to use Induction properly?

I would like to prove the following equation using induction. However that seems somehow impossible at least for me: $\sum\limits_{k=1}^{2n} {(-1)^k \cdot k^2}=(2n+1)\cdot n$ I tried to show that ...
2
votes
3answers
175 views

How to prove through induction

How can I prove by induction that $$\binom{2n}n<4^n\;?$$ I have solved for the base case, $n=1$, and have formulated the induction hypothesis. I was thinking about Pascal's identity for the ...
2
votes
3answers
81 views

Showing $1+2+\cdots+n=\frac{n(n+1)}{2}$ by induction (stuck on inductive step)

This is from this website: Use mathematical induction to prove that $$1 + 2 + 3 +\cdots+ n = \frac{n (n + 1)}{2}$$ for all positive integers $n$. Solution to Problem 1: Let the ...
0
votes
3answers
26 views

question on prove by induction that for each n$\in\mathbb{N}_{\ge2}$, $n^2$< $n^3$

I have to prove by induction that for each n$\in\mathbb{N}_{\ge2}$, $n^2$< $n^3$. If I try to prove for P(1) I end up with 1 < 1. Is this right? Why does it or does it not make sense?
2
votes
2answers
73 views

Is there a much simpler proof for Euler factorial formula?

Euler formula for factorial stated as follows Theorem [Euler]: For any non negative integers $a$ and $n$ such that $a\geq n$ $$ n!=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(a-k)^n$$ Proving this ...
4
votes
1answer
67 views

Dynamical system $x_{n+1} = \frac{1}{2}(x_n - \frac{1}{x_n}) \ \ , \ \ n = 0, 1 , 2,…$

Consider the dynamical system $$ x_{n+1} = \frac{1}{2}(x_n - \frac{1}{x_n}) \ \ , \ \ n = 0, 1 , 2,... $$ So by using the substitution $x_n = \cot(y_n)$, I have found: $$ x_n = \cot(\cot^{-1} ...
0
votes
0answers
25 views

Help on Proof By Induction

We had to prove the following algorithm by induction: $ a^n = a^{n/2*2} = a^{n/2}*a^{n/2} $ if $n$ is even $ a^n = a^{\frac {n-1}2*2}*a = a^{\frac {n-1}2} * a^{\frac {n-1}2} * a $ if $n$ is ...