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
54 views

basic mathematical induction problem

Prove that for some $b \in \mathbb{N}$, $(\sqrt{2})^n > n$ for every $n \geq b$ Find such a $b \in \mathbb{N}$. Prove that $\forall$$n \geq b$, $(\sqrt{2})^n > n$ How would I approach ...
2
votes
2answers
95 views

Show that $f(x)=0$ for all $x \in [a,b]$.

I have the following problem: Suppose that $f$ is continuous on $[a,b]$ and suppose that for all $x \in [a,b]$, $f(x) \geq 0$ and $f(x)\leq \int_a^x f(t)dt$. Show that $f(x)=0$ for all $x \in ...
2
votes
1answer
73 views

If there is an injection $f: X \to Y$ with $m=n$ then $f$ is a bijection.

The Statement of the Problem: Let $X,Y$ be finite sets with $ \lvert X \rvert = m $ and $ \lvert Y \rvert = n $. Prove the following statement by induction on $ m \ge 1$: If there is an injection ...
0
votes
2answers
21 views

For any prime $p ≠ 2,5$, prove there are at most four values of the last digit of any power $p^{i}$?

I am currently working on this question and I am thoroughly stuck. I believe that this question is saying that for any prime $p$, there will be four or less numerals $p-1$ that exist in the numeral ...
4
votes
1answer
60 views

Transfinite Induction in Peano Arithmetic

I have heard that Peano Arithmetic (PA) cannot perform transfinite induction up to $\varepsilon_0$. This seems to imply that it can induct up to smaller ordinals, like $\omega$ or $\omega^\omega$ or ...
-1
votes
2answers
68 views

Proving by induction $2^k - 1 = 1+\cdots +2^{k-1}$

How can I show: $$2^k - 1 + 2^{(k+1)-1} = 2^{k+1} - 1$$ I am trying to prove this by induction: $$2^k - 1 = 1+\cdots +2^{k-1}$$ and proved the base case: $2^2-1 = 1+2^1$ as $2^2-1=3$ and ...
2
votes
0answers
60 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
2
votes
2answers
40 views

Proving that for Fibonacci numbers $a_n \lt (\frac {1 + \sqrt 5} 2)^n$ for $n \ge 1$

I'd like to prove that for Fibonacci numbers $a_n \lt \left(\frac {1 + \sqrt 5} 2\right)^n$ for $n \ge 1$. I suppose it needs induction so, after verifying the trivial case $n=1$, the inductive step ...
1
vote
3answers
61 views

Prove that $(n!)^{\frac{1}{n}} < ((n+1)!)^{\frac{1}{n+1}}$

I have been tasked with proving that $(n!)^{\frac{1}{n}} < ((n+1)!)^{\frac{1}{n+1}}$ for every integer $n \geq 1$. My instinct is to use induction, but I have gotten stuck. Base Case - $n=1$: ...
0
votes
1answer
44 views

Show that $\sum_{r=1}^nu_r=u_{n+1}-(n+2)$ given $u_1=2\,,u_{k+1}=2u_k+1\,,u_n=3\times2^{n-1}-1$

The sequence $u_1$, $u_2$, $u_3$,... is defined by $$u_1=2\,,\,\,\,\,\,\,\,\,\,u_{k+1}=2u_k+1$$ $$u_n=3\times2^{n-1}-1$$ Show that $$\sum_{r=1}^nu_r=u_{n+1}-(n+2)$$ Prove that it is true for $n=1$ ...
0
votes
2answers
71 views

Proving by strong induction for a sequence of integers, $2^n$ divides term $n$

Provided the following sequence of integers $t_1, t_2, t_3$,... is defined as: $t_1 =4, t_2 =8$ and $t_n= $ $ 6t_n$$_-$$_1$ - $4t_n$$_-$$_2$ for all integers $n \geq 3$ How do we prove that $2^n$ ...
0
votes
1answer
31 views

Axiom of Induction Question

I have to use the axiom of induction to prove the summation of k^3 from 0 to n is $(n(n+1)/2)^2$. Here's what I have so far: Let P(n) be the assertion that $0^3+1^3+⋯+n^3=(n(n+1)/2)^2$ Base Case ...
0
votes
2answers
71 views

Show that $\sum_{r=1}^nu_r=u_{n+1}-(n+2)$ [closed]

Here's the information from the question The sequence $u_1$, $u_2$, $u_3$,... is defined by $$u_1=2\,,\,\,\,\,\,\,\,\,\,u_{k+1}=2u_k+1$$ Then I was asked to prove that, for all $n\ge1$ ...
2
votes
2answers
41 views

Prove by induction that $u_n=3\times2^{n-1}-1$ for all $n\ge1$

The sequence $u_1$, $u_2$, $u_3$,... is defined by $$u_1=2\,,\,\,\,\,\,\,\,\,\,u_{k+1}=2u_k+1$$ Prove by induction that, for all $n\ge1$, $$u_n=3\times2^{n-1}-1$$ You first have to prove that $u_1=2$ ...
1
vote
4answers
83 views

Prove that if $k \in \mathbb{N}$, then $k^4+2k^3+k^2$ is divisble by $4$

I am trying to solve by induction and have established the base case (that the statement holds for $k=1$). For the inductive step, I tried showing that the statement holds for $k+1$ by expanding ...
6
votes
8answers
107 views

How to show that $6^n$ always ends with a $6$ when $n\geq 1$ and $n\in\mathbb{N}$

Is there a proof that for where $n$ is a natural number $$6^n$$ will end with a $6$? I can understand conceptually that $6\cdot 6$ ends with $6$ and then multiplying that by $6$ will still end with ...
0
votes
1answer
33 views

Write an inductive proof that if there is a surjection $ f : \lceil m \rceil → \lceil n \rceil $ then $m ≥ n$.

Here's the problem: Write an inductive proof that if there is a surjection $ f : \lceil m \rceil → \lceil n \rceil $ then $m ≥ n$. Where I Am: I assume that I should induct on $n$ and come to the ...
0
votes
2answers
44 views

Prime Factorization

Let $n\ge0$. What is the power of $2$ in the prime factorization of $(2^n)!\,$? Prove that the value is correct. So far I've conjectured the value to be $2^n - 1$. This is true for $n=0,1,2,3,4$. ...
0
votes
2answers
33 views

How can we prove by induction the relation $P(x,y)$?

How can we prove by induction the relation $A(x,y)>y, \forall x,y$, where A(x,y) is the Ackermann function? When we have to prove a relation $P(n), n\geq 0$, we do the following steps: we ...
0
votes
1answer
39 views

Expressing a function's value using finite differences

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ and let $x = (x_0, x_1, x_2, \dots)$ be a sequence of pairwise distinct real numbers. For every $n \in \{1, 2, \dots\}$ and every ordered $(n+1)$-tuple ...
4
votes
4answers
121 views

How to deduce that $1\cdot 1 + 2\cdot 1 + 2\cdot 2 + 3\cdot 1+3\cdot 2+3\cdot 3 +…+(n\cdot n) = n(n+1)(n+2)(3n+1)/24$

I know how to reason $$1\cdot2 + 2\cdot3 + 3\cdot4 + n(n-1) = \frac{1}{3}n(n-1)(n+1)$$ However, I'm stuck on proving $$1\cdot1 + (2\cdot1 + 2\cdot2) + (3\cdot1+3\cdot2+3\cdot3) + \cdots +(n\cdot ...
0
votes
1answer
25 views

Is this a valid strong induction proof? (2 base cases)

I am a university student and I was self-teaching myself induction methods. I did question (3)(b). The answer to (3)(a) is g n = 2^n + 1 for n is a positive natural number. My solution differs from ...
3
votes
5answers
143 views

Prove that $2^n\le n!$ for all $n \in \mathbb{N},n\ge4$

The problem i have is: Prove that $2^n\le n!$ for all $n \in \mathbb{N},n\ge4$ Ive been trying to use different examples of similar problems like at: ...
1
vote
1answer
20 views

Help with the Inductive step in mathematical Induction?

I just started working on Induction, and I have one particular problem that I don't understand: Prove that $1+3+5+...+(2n−1)=n^2$ for any integer $n≥1.$ $n = 1$ : $1 = 1^2$ $n = k$ : ...
6
votes
2answers
95 views

Prove that $\forall n > 1 \quad2^n - 1 \pmod n \neq 0$

Prove that $\forall n > 1, \quad2^n - 1 \pmod n \neq 0$ I've thought of the induction but I can't figure out how to prove the step. Fermat's theorem (and its variations) aren't particularly useful ...
4
votes
1answer
88 views

Integer induction without infinity

In ZFC minus infinity (let us call this T), one can still define ordinals, and then define integers as ordinals all of whose members are zero or successor ordinals. I am looking for a formula $\psi$ ...
0
votes
1answer
29 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
56 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
56 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
39 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
46 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
87 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 ...
-2
votes
1answer
52 views

The King & Mathematicians [closed]

The king summoned the best mathematicians in the kingdom to the palace to find out how smart they were. The king told them:" I have placed white hats on some of you and black hats on the others. You ...
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
39 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
53 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
24 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
72 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
68 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
35 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
44 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
53 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
101 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
62 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
40 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 ...