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
votes
1answer
98 views

Proving by induction on the number of vertices that: every acyclic simple graph is bipartite

Prove that every acyclic simple graph is bipartite, by the use of induction. I have quite some trouble with induction. Specifically, I know that acyclic graphs have at least one vertex that has a ...
3
votes
3answers
44 views

Why are two base cases needed to prove that $n<2^n$ for all $n\geq 0\,$?

So I understand more than one base case is needed when there is a recurrence relation like the Fibonacci sequence. But I don't understand why two base cases are needed in the below example. Is there ...
3
votes
4answers
58 views

How to prove $ \sum\limits_{k=1}^{n}\frac{k}{(k+1)!}=1-\frac{1}{(n+1)!}$ using induction?

This is as far as I get. I get stuck here because both sides to not equal each other, but I am not sure what I am doing wrong. $$ \sum\limits_{k=1}^{n}\frac{k}{(k+1)!}=1-\frac{1}{(n+1)!}$$ Assume: ...
1
vote
4answers
60 views

Solution verification: Prove by induction that $a_1 = \sqrt{2} , a_{n+1} = \sqrt{2 + a_n} $ is increasing and bounded by $2$

I have the following recursive relation (sequence): \begin{align} a_1 = \sqrt{2}, \quad a_{n+1} = \sqrt{2 + a_n} \end{align} My Try: I'm a little skeptical of my manipulations near the end but it ...
0
votes
1answer
26 views

Prove by induction $n^{1/n} ≤ \frac{n+1}{2}$

The problem Prove by induction: $n^{1/n} ≤ \frac{n+1}{2}$ Attempt at solution I started off with the usual steps for an MI problem. We start with the $P_1$ case: for $P_1$, LHS = 1 and RHS = 1 ...
0
votes
1answer
30 views

context-free languages operation closure

The following operation is defined on formal languages. $ operation1(L) = \lbrace w \ | \ wxy \in L, \ \forall x \forall y \ (|x|=|w|) \ \wedge (|y| = |w| ) \rbrace $ Prove that context-free ...
2
votes
1answer
34 views

Use Induction to Show $(1+a)^n \ge 1 + na$

If $a$ $\in$ $\mathbb R$ $\ni$ $a > -1$, then ($\forall n$ $\in$ $\mathbb R$) ($(1+a)^n \ge 1 + na$) My main concern is twofold: Firstly, I am concerned that constant $a$ in the proposition may ...
1
vote
4answers
59 views

Proving by induction that $n^2 - 7n - 2$ is divisible by $2$

Now proving by induction is fairly simple. However, this is a multiple choice problem whose answers don't make any sense to me. The actual problem goes as follows: To prove by induction that $n^2 - ...
1
vote
1answer
33 views

How can i prove using induction that the Hadamard matrices are orthogonal?

I can't figure out how to prove using induction that the dot product of 2 rows in a Hadamard matrix is 0. I've always thought of it as just a property of the type of matrix.
1
vote
1answer
38 views

Proof of Newton Girard formula symmetric polynomials

Newton Girard formula states that for $k>2$: \begin{equation} p_k=p_{k-1}e_1-p_{k-2}e_2+\cdots +(-1)^{k}p_1e_{k-1}+(-1)^{k+1}ke_{k} \end{equation} where $e_i$ are elementary symmetric functions and ...
0
votes
3answers
50 views

Proof By Induction $2^n \ge n^2$ for $n\ge4$

I am trying to prove the following, and here is what I have done: Can somebody help to complete this? $2^n \ge n^2$ for $n\ge 4$ $n=4$, LHS: $2^4 = 16$, RHS: $4^2=16$, $16=16$ Therefore TRUE Assume ...
0
votes
1answer
36 views

Proving $2n-8<n^2-8n+14$ for all $n\geq 7$ by induction

For what values of the natural number $n$ is $2n-8 < n^2-8n+14$? (must use induction) I have determined that $n$ appears to work for all values except $n=4,5,6$. I was wondering if this proof ...
1
vote
5answers
54 views

Mathematical Induction on a Subset of the Natural Numbers

I am given a strict inequality of the form $$ 2n - 8 < n^2-8n+14, $$ where $n$ belongs to the set of natural numbers $\mathbb{N}$ (in this case $n$ does not equal 0). I am asked, for what values ...
4
votes
4answers
91 views

Prove $\sum_{i=2}^{n}\frac{1}{(n-1)n}$ = $\frac{(n-1)}{n}$ using induction.

I need to prove $\sum_{i=2}^{n}\frac{1}{(i-1)i}$ = $\frac{(n-1)}{n}$ using induction. I am getting stuck midway through the inductive step. Here is what I have: $\forall n\geq 2$, where ...
1
vote
4answers
66 views

Prove that for all positive integers $n$, $2^1+2^2+2^3+…+2^n=2^{n+1}-2$ [duplicate]

I want to prove that for all positive integers $n$, $2^1+2^2+2^3+...+2^n=2^{n+1}-2$. By mathematical induction: 1) it holds for $n=1$, since $2^1=2^2-2=4-2=2$ 2) if $2+2^2+2^3+...+2^n=2^{n+1}-2$, ...
2
votes
2answers
32 views

Proof By Induction $n^2 > 3n$ where $n\ge 4$

I am trying to prove the following example, however I seem to be getting a little stuck: For $n\in\mathbb N$, $n\ge 4, n^2>3n$ What I have Done: Base Case:$ n=4$, LHS: $4^2 = 16$, RHS: $3\cdot 4 ...
0
votes
2answers
57 views

Explaining why proof by induction works [duplicate]

I am learning math proofs for the first time. So I cannot discern the reason for all the details in a proof. Here's the statement of mathematical induction: For every positive integer $n$, let ...
1
vote
2answers
25 views

Proof by induction of the Inequality of Harmonic numbers: $H_{2^n} \ge 1+ \frac n2$

My question is, for the question below, in the inductive step, where does $\dfrac{1}{2^{(k+1)}}$ come from?And where does $2^k$ come from in the third last step?
1
vote
1answer
32 views

How many comparisons does it take to find a number in a grid of numbers arranged in an $N \times N$ square

We have an $N \times N$ squares, filled with integer numbers monotonically increasing in "right" and "down" directions. So from any point, if you move left the number will get bigger, or if you go ...
-1
votes
2answers
56 views

Union-closed families of sets (A problem about induction)

$A$ and $B$ are two sets If $A,B \in F,$ then $A \cup B \in F$. Prove by induction that this property applies to a countable number of sets. If $A_i \in F,i \in \mathbb{N}$, then $ ...
-2
votes
3answers
35 views

Proof by induction. how can I solve?

How can I demonstrate this equality: $$1+2q+3q^2...+nq^{n-1}=\frac{1-(n+1)q^n+nq^{n+1}} {(1-q)^2} $$ My attempt: if $n=1$ $$1=\frac{1-2q+q^2} {(1-q)^2}=1$$ Now i demonstrate this equality: ...
0
votes
5answers
72 views

Mathematical induction [duplicate]

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
88 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 ...
4
votes
4answers
59 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
102 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
68 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
42 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
43 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
20 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
38 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
80 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
55 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
201 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
29 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
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
94 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
59 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
58 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
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
70 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 ...