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
2answers
34 views

Mathematical induction

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...
5
votes
5answers
82 views

Prove by mathematical induction: $\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{n^2}>1$

Could anybody help me by checking this solution and maybe giving me a cleaner one. Prove by mathematical induction: $$\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{n^2}>1; n\geq2$$. So after I check ...
3
votes
5answers
51 views

Proving $2^n -1 = \sum_{i=0} ^{n-1} 2^i$ for all $n\geq 1$ by induction

I'm practicing proofs by induction, and equalities seem to be the toughest for me. Can somebody please help to prove that for all integers $n \geq 1$: $$ 2^n -1 = \sum \limits _{i=0} ^{n-1} 2^i\;? $$ ...
4
votes
5answers
93 views

Proving $6^n - 1$ is always divisible by $5$ by induction

I'm trying to prove the following, but can't seem to understand it. Can somebody help? Prove $6^n - 1$ is always divisible by $5$ for $n \geq 1$. What I've done: Base Case: $n = 1$: $6^1 - 1 = ...
0
votes
4answers
63 views

Proof by Induction $3^n > n^3$

I am trying to prove the following, however I'm stuck at the Induction hypothesis Prove by induction that, for all integers $n$, if $n\geq 5$, then $3^n>n^3$ What I have Done: Base Case: $n ...
-1
votes
1answer
41 views

How can I prove by mathematical induction that $\sum_{i=0}^n i^4 = (\sum_{i=0}^n i)^3$?

How can I prove by mathematical induction that $$\sum_{i=0}^n i^4 = (\sum_{i=0}^n i)^3$$ ? I see easily that it holds for $i=0$. Using the inductive hypothesis, I get: $$\sum_{i=0}^{n+1} i^4 = ...
3
votes
2answers
39 views

Multiple part problem concerning the proof that $\sum_{k=1}^n k^3=\left(\frac{n(n+1)}{2}\right)^2$ by induction

So I'm having trouble with $c,d$ and $e$. For $c$ so far I have: Inductive Hypothesis: $(\frac{n(n+1)}{2})^2 = (\frac{(k+1)(k+2)}{2})^2$ is that correct?
0
votes
1answer
17 views

How to prove this proposition with induction

Let $P(x)$ be a polynomial of degree $n$ in the field $\mathbb{R}$ such that $a_n,\ldots,a_0$ are the coefficients. How can I show through induction that if there is at least one coefficient $a_i$ ...
1
vote
2answers
34 views

Proving $10^n \equiv 1 \pmod 3$ for all $n\geq 1$ by induction

Prove that $10^n \equiv 1 \pmod 3$ for all positive integers $n$ by mathematical induction. Can someone please help me in solving this problem and explain what's going on? Any guidance would be ...
-4
votes
3answers
71 views

Proving that $2^n+1\leq 3^n$ by induction

I need to prove the following using mathematical induction: $$2^n+1\leq 3^n\qquad\forall n\in\Bbb{Z^+}$$ Been working on this problem for a while and cannot figure it out. Any guidance or help would ...
0
votes
1answer
51 views

Where to make induction?

I have read a exercise that states as follows; Use induction to prove that $\forall n \in \mathbb{N}: \forall m \in \mathbb{N}: n<m \Rightarrow \exists r \in \mathbb{N}: n+r=m.$ Sugestion. ...
0
votes
5answers
66 views

How to Prove with Mathematical Induction $3^n > n^2$

How do I prove that $3^n > n^2$ with mathematical induction? I thought I had the correct answer but my teacher says its wrong. I let $n=1$ for the initial case and it works. I then assumed $n=k$ ...
1
vote
4answers
199 views

Prove by strong induction that $2^n$ divides $p_n$ for all integers n ≥ 1 [duplicate]

Let $p_1 = 4$, $p_2 = 8$, and $p_n = 6p_{n−1} − 4p_{n−2}$ for each integer $n ≥ 3$. Prove by strong induction that $2^n$ divides $p_n$ for all integers $n ≥ 1$ I got up to the base step where ...
2
votes
2answers
28 views

Prove ${4n \choose 2n} = {\frac{1\cdot3\cdot5\cdots(4n-1)}{(1\cdot3\cdot5\cdots(2n-1))^{2}}}{2n \choose n}$

Prove that prove $\dbinom{4n}{2n} = \dfrac{1\cdot3\cdot5\cdots(4n-1)}{(1\cdot3\cdot5\cdots(2n-1))^2} \dbinom{2n}{n}$ using mathematical induction. I have looked all over the internet, been able to ...
0
votes
1answer
52 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
93 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
72 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
58 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
54 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
39 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
60 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
67 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
29 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
70 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
79 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
105 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
31 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
24 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
139 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
84 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
86 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
54 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
61 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
37 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
84 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
51 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 ...