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

2
votes
2answers
27 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
39 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
139 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{ ...
-2
votes
1answer
18 views

show that $\neg(p_1 \vee p_2 \vee… \vee p_n)$ is equivalent to $\neg p_1 \wedge \neg p_2 \wedge… \wedge \neg p_n$ by induction

Use mathematical induction to show that $\neg(p_1 \vee p_2 \vee... \vee p_n)$ is equivalent to $\neg p_1 \wedge \neg p_2 \wedge... \wedge \neg p_n$ whenever $p_1,p_2,...,p_n$ are propositions. So ...
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
64 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
51 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
216 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
30 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
56 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
34 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
32 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
49 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
189 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
45 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
33 views

Proofing Induction Mathematics

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 ...
4
votes
2answers
64 views

Proving that $3^n<n!$ when $n\geq 7$

It's been 10 years since my last math class so I'm very rusty. How would I go about proving $$3^n < n!$$ where $n \geq 7$? I understand that factorials grow faster than set values with a variable ...
2
votes
4answers
80 views

Rewrite $\sum_{i=0}^{n-1} (2i+1)=n^2$ to start induction from $k = 0$?

I'm trying to learn mathematical induction. The text asks for being totally rigorous i.e start induction from $k=0$. I want to prove that $$\sum_{i=0}^{n-1} (2i+1)=n^2,$$ i.e. the sum of the first ...
0
votes
2answers
57 views

Construction of Natural Numbers

I am trying to prove that the natural numbers can be constructed from the product of a power of $2$ and an odd number. For all $n \neq 0$ in the natural numbers, $n = (2k+1)(2^p)$, where $k$ and $p$ ...
13
votes
4answers
228 views

Proving $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$ by induction

How can I prove by induction that $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$? My guess is that there must be another form to express the sum of nested square roots, but I don't know how ...
4
votes
1answer
41 views

Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$. The hint was to use induction. ...
0
votes
3answers
46 views

Find a formula for $ 1\times3^0 + 3\times3^1 + 5\times3^2 + … +(2n+1)\times3^n$.

The original exercise is to find a formula for this and prove it via induction. However, I am having a problem deriving such a formula. How do you normally approach this types of problems, is it a ...
0
votes
1answer
21 views

How to go about induction that deals with inequalitites

The only thing i've been able to do is to prove it for 1. How do i go about prvoing it for k+1?
0
votes
1answer
31 views

Nim Variant - Strong Induction Proof

Here we will play a variant of Nim where there is an additional move option in some cases. If two or more piles have the same number of stones, a player may remove the same number of stones from ...
0
votes
1answer
29 views

How to perform induction step in this question?

Q:Prove By induction $2^{n+1} > n^2$ for all positive integers. Step 1: Base case: $n=1$, we get $4>2$ Step 2: Induction hypothesis: $n=k, 2^{k+1} > k^2$ Step 3: Induction Step: to ...
-1
votes
1answer
119 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
51 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
78 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
75 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
29 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
39 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
36 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
65 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
2answers
67 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
49 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
56 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
43 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
95 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 ...