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

Can I use induction by $|V|$ here?

Show that any connected, undirected graph $G = (V,E)$ satisfied $|E|≥|V|-1$. Can I use math induction by $n = |V|$ here (remove and add vertex)?
4
votes
1answer
34 views

Principle of mathematical induction to prove well ordering principle for set of rationals.

I am not being able to find what is wrong in this proof. statement: For any set of rationals there is a least element in the set. Hypothesis: $p(k)$=For set of k rationals there exist a least ...
1
vote
0answers
29 views

Proving recursive formula via induction leads to extra term?

I have been asked the following question, and despite spending the last 30 minutes on it, have not come up with a good result: Define f(1) = 2, and f(n) = f(n-1) + 2n for all n ≥ 2. Find a ...
2
votes
2answers
77 views

Proving that $P\left ( \bigcup_{i=1}^{n}A_{i} \right )\leq \sum_{i=1}^{n}P(A_{i})$ by induction

Proposition 1: Let $A_{1},\dots, A_{n}$ be events in the probability space $(\Omega,\mathcal{F},P)$. Then $$P\left ( \bigcup_{i=1}^{n}A_{i} \right )\leq \sum_{i=1}^{n}P(A_{i}).$$ Let's start with a ...
0
votes
0answers
27 views

Proof for maximum number of leaves in a tree with a given hopping distance

Hi I need help to prove the following for tree graphs which I believe is true: A tree with hopping distance $k$ (i.e. the most number of edges that any two vertices are apart) and n leaves either has ...
3
votes
7answers
117 views

Proving $\frac{1}{1\cdot3} + \frac{1}{2\cdot4} + \cdots + \frac{1}{n\cdot(n+2)} = \frac{3}{4} - \frac{(2n+3)}{2(n+1)(n+2)}$ by induction for $n\geq 1$

I'm having an issue solving this problem using induction. If possible, could someone add in a very brief explanation of how they did it so it's easier for me to understand? $$\frac{1}{1\cdot3} + ...
27
votes
1answer
332 views

Uses of “Collatz induction”?

The Collatz conjecture is equivalent to the following "induction principle": If $P(0) \land P(1) \land (\forall{x} P(3 \cdot x + 2) \implies P(2 \cdot x + 1)) \land (\forall x P(x) \implies P(2 \cdot ...
-3
votes
2answers
73 views

Proving $25^{n+1} -24n +5735$ is always divisible by $576$ [closed]

Prove $25^{n+1} -24n +5735$ is always divisible by $576$ using mathematical induction. Not able to simplify the expression after replacing $n=k+1$ Please help... Thanks!
2
votes
2answers
104 views

I have to prove by mathematical induction that $\frac{(2n)!}{n!(n+1) !}$ is a natural number for all $n\in\mathbb{N}$.

I have to prove by mathematical induction that $$\frac{(2n)!}{n!(n+1) !}$$ is a natural number for all $n\in\mathbb{N}$. Any help would be really awesome.
0
votes
1answer
33 views

Check my solution: For the recurrence $a_{n+3}=a_{n+2}+a_{n+1}+a_n$ where $a_1=a_2=a_3=1$, prove that $a_n\leq 2^{n-2}$.

I need help with verifying my solution for the homework question: For the recurrence $a_{n+3}=a_{n+2}+a_{n+1}+a_n$ where $a_1=a_2=a_3=1$, prove that $a_n\leq 2^{n-2}$, $\forall n>1$ ...
2
votes
6answers
102 views

Prove $2(7^n) + 3(5^n)-5$ is always divisible by $24$ [closed]

Prove $2(7^n) + 3(5^n)-5$ is always divisible by $24$ by Mathematical Induction. Can anyone please give me hints for this question.. Thanks.
1
vote
1answer
59 views

Prove that sequence $a_1 = \sqrt{2}$, $a_{n+1} = \sqrt{2 + a_n}$ is bounded above by 3

I need a little bit of help (just a hint, please) with an induction proof on this sequence, which I need to prove is bounded above by 3. $$ a_1 = \sqrt{2} $$ $$ a_{n+1} = \sqrt{2 + a_n} $$ My ...
1
vote
1answer
58 views

Understanding a step in this proof by induction

Here's an example I discovered in a book. Prove inequality when $a\ge-1$:$$(1 + a)^n \ge 1 + na.$$ Let's use mathematical induction. Then $n = 1$ left and right parts are equals. Let's ...
5
votes
4answers
164 views

Proving that $1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots+\frac{1}{2n-1}-\frac{1}{2n}=\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{2n}$

I have written the left side of the equation as $$\left(1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{2n-1}\right)-\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\cdots+\frac{1}{2n}\right).$$ I don't know how ...
0
votes
3answers
52 views

Prove $1^3+2^3+…+n^3 = (1+2+…+n)^2$ for all positive integers $n$. [duplicate]

My approach is to solve this by induction. Base case: $n=1$ $1^3 = 1^2 = 1$ Inductive Step: Suppose that $1^3+2^3+...+n^3 = (1+2+...+n)^2$ holds for all positive integers $n$. We use that to ...
-1
votes
3answers
65 views

Using induction to prove that $2 \mid (n^2 − n)$ for $n\geq 1$

Use induction to prove that, for all $n \in \mathbb{Z}^+$, $2\mid (n^2 − n)$. That is, I am supposed to use induction to prove that $(n^2 − n)$ can be divided by $2$ when $n$ is a positive ...
2
votes
2answers
45 views

Proving $\sum_{j=1}^n \frac{1}{\sqrt{j}} > \sqrt{n}$ with induction

Problem: Prove with induction that \begin{align*} \sum_{j=1}^n \frac{1}{\sqrt{j}} > \sqrt{n} \end{align*} for every natural number $n \geq 2$. Attempt at proof: Basic step: For $n = 2$ we have $1 ...
1
vote
1answer
32 views

Is this proof by induction that $|\Bbb Q^n|=\aleph_0$ correct?

Is this proof by induction that $|\Bbb Q^n|=\aleph_0$ correct? Suppose I know that $|\Bbb Q|=|\Bbb N|=|\Bbb N^2|=\aleph_0\cdot\aleph_0=\aleph_0$. Proof: Suppose $|\Bbb Q^n|=\aleph_0$, then ...
6
votes
3answers
1k views

People sitting in a circle chewing gum

Ten people are sitting in a circle of ten chairs, chewing gum. Each person spits out his or her gum and places it either under his or her own chair or under an immediately adjacent chair. How many ...
3
votes
4answers
74 views

Prove by induction: $\frac{1}{2!}+\frac{2}{3!}+\cdots+\frac{n}{(n+1)!}=\frac{n!-1}{n!}$

Prove $$\frac{1}{2!}+\frac{2}{3!}+\cdots+\frac{n}{(n+1)!}=\frac{n!-1}{n!}.$$ My problem with this is that it doesn't hold for the base case: $n=1$. This question is from the book "Abstract ...
1
vote
1answer
96 views

Prove that “No one likes Reggae music” is the same as “Everyone does not like Reggae music”.

I interpreted this as a case of the extension of De Morgan's Law to quantifiers. https://en.wikipedia.org/wiki/De_Morgan%27s_laws#Extensions I know that similar questions have been asked before about ...
2
votes
5answers
53 views

Showing that $\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$ for all $n\geq 1$

Show that $$\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$$ for all $n\geq 1$ I need this in order to complete my proof that $1 + \frac{n}{2} \leq H_{2^n}$, but ...
2
votes
2answers
52 views

Show by induction that $F_n \geq 2^{0.5 \cdot n}$, for $n \geq 6$

I have the following problem: Show by induction that $F_n \geq 2^{0.5 \cdot n}$, for $n \geq 6$ Where $F_n$ is the $nth$ Fibonacci number. Proof Basis $n = 6$. $F_6 = 8 \geq 2^{0.5 \cdot ...
6
votes
4answers
57 views

Proving $\sum_{i=1}^n 2^i = 2^{n+1} - 2$ using strong induction [duplicate]

I just started learning proof by induction in class, but got a problem requiring proof by strong induction. Here is the problem. Prove by strong induction: $$\sum_{i=1}^n 2^i = 2^{n+1} - 2$$ ...
0
votes
3answers
58 views

Evaluate: binomial theorem

Show: $$(x+1)^m=\sum_{k=1}^{m}\binom{m}{k}x^k$$ Can somebody help me in showing the above stated problem?
1
vote
1answer
52 views

How to use induction to show that $\delta(\mathcal G_1), \ldots, \delta(\mathcal G_n) $ are independent?

I have proven that if the systems $\mathcal G$ and $\mathcal H$ are independent then so are the Dynkin systems $\delta(\mathcal G)$ and $\delta(\mathcal H)$. Now I'd like to generalize it to $n$ ...
3
votes
4answers
129 views

Prove using mathematical induction that $x^{2n} - y^{2n}$ is divisible by $x+y$

Prove using mathematical induction that $(x^{2n} - y^{2n})$ is divisible by $(x+y)$. Step 1: Proving that the equation is true for $n=1 $ $(x^{2\cdot 1} - y^{2\cdot 1})$ is divisible by $(x+y)$ ...
0
votes
1answer
42 views

How do I convert a sum to an algebraic expression?

Something something Riemann sum to integral is the most that I remember. I just don't remember how we did it or whether or not that would be the best method for doing it. Let $ \theta(n) = ...
0
votes
1answer
83 views

Find the number of flags of different types using induction

A flagpole is $n$ feet tall. On this pole we display flags of the following types: red flags that are $1$ foot tall, blue flags that are $2$ feet tall, and green flags that are $2$ feet ...
10
votes
3answers
571 views

Why can mathematical induction only be used with natural numbers?

So, I've been learning Principle of Mathematical Induction as part of my syllabus, and so far, I've found it to be really fun to do. There's one thing I don't understand though (and none of my ...
0
votes
1answer
55 views

A vessel contains $x$ amount of milk out of which $y$ amount is taken out and replaced with water $n$ times.

There is a formula in my book for questions of type, A vessel contains $x$ amount of milk out of which $y$ amount is taken out and replaced with water. After $n$ such operations what will be the ...
2
votes
4answers
60 views

Prove by induction that $\sum_{k=1}^{n} k^3 = \bigg( \sum_{k=1}^{n}k\bigg)^2$ [duplicate]

Show the following for all positive integers using proof by induction: $$\sum_{k=1}^{n} k^3 = \bigg( \sum_{k=1}^{n}k\bigg)^2$$ Base case (n = 1) passes: $1^3 = 1^2$ We assume the following: ...
0
votes
1answer
26 views

defining a sequence of numbers L n≥1, and prove something about it

So i was given this question just to try for practice to test our knowledge and i'm really confused on how to go about this question. How should i go about this question, i'm confused with the greek ...
1
vote
2answers
96 views

Prove by induction that $n! > 2^n$

Suppose that when $n=k$ $(k\geq4)$, we have that $k!>2^k$. Now, we have to prove that $(k+1)!\geq2^{k+1}$ when $n=(k+1)$ $(k\geq4)$. $$(k+1)! = (k+1)k! > (k+1)2^k \text{ (since }k!>2^k)$$ ...
2
votes
3answers
76 views

Proving $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$ using strong induction

The question says $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$. Here is my proof by strong induction: Base case: $10\cdot0=0$. Let $k\geq 0$, and suppose that for any $m\leq k$ we have ...
2
votes
1answer
82 views

Weird Induction…?

I was watching this video earlier and I couldnt figure out why the following step was possible. This is the original problem: $\sum_{i = 0}^{n} \binom{n + i}{i} = \binom{2n + 1}{n + 1}$ At one ...
3
votes
3answers
53 views

Proving $\sum_{i=1}^n\frac{1}{i(i+1)(i+2)}=\frac{n(n+3)}{4(n+1)(n+2)}$ for $n\geq 1$ by mathematical induction

Prove using mathematical induction that $$\frac{1}{1\cdot 2\cdot 3} + \frac{1}{2\cdot 3\cdot 4} + \cdots + \frac{1}{n(n+1)(n+2)} = \frac{n(n+3)}{4(n+1)(n+2)}.$$ I tried taking $n=k$, so it makes ...
3
votes
4answers
112 views

Proving that $1\cdot3+3\cdot5+5\cdot7+\cdots+(2n-1)(2n+1)={n(4n^2+6n-1) \over 3}$ by induction for $n\geq 1$

Prove using mathematical induction that $$1\cdot3+3\cdot5+5\cdot7+\cdots+(2n-1)(2n+1)= {n(4n^2+6n-1) \over 3}.$$ Step 1: If we assume that the equation is true for a natural number, $n=k$, ...
0
votes
2answers
37 views

I need help proving the base case for a mathematical induction proof

I know how mathematical induction works and the generic algorithm of proving a statement by the Principle of Mathematical Induction, but I'm having trouble proving the base case for a particular ...
2
votes
3answers
73 views

Product of the difference of $n$th roots of $-1$ [closed]

If $w_1,w_2,\ldots,w_n$ are the $n^{\text{th}}$ roots of $-1$, then how can we prove that by mathematical induction $$(w_2-w_1 )(w_3-w_1 )\cdots(w_n-w_1 )=\frac n{w_1}?$$
1
vote
1answer
46 views

Confused by inductive proof of associative law

In Artin's book he proves the associativity of a $n$-element product. It says as follows: i) the product of one element is the element itself. ii) the product $a_1a_2$ is given by the law of ...
2
votes
3answers
70 views

Prove that $\sum_{d|n}\phi(d)=n$ where $\phi$ is the Euler's phi function, $n,c\in\mathbb{N}$

Here is a very elementary number theory proof using strong induction. Please mark/grade. Prove that $$\sum_{d|n}\phi(d)=n$$where $\phi$ is the Euler's phi function, $n,d\in\mathbb{N}$ First, ...
3
votes
0answers
42 views

Induction Can't Prove Complexity?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
4
votes
1answer
54 views

Mathematical induction inequality involving sines

Let $0<A_i<\pi$ for $i=1,2,3,\ldots,n$. Use mathematical induction to prove that $$\sin A_1+\sin A_2+\cdots+\sin A_n\le n \sin\left(\frac{A_1+A_2+A_3+\cdots+A_n} n\right)$$ where $n\ge 1$ is a ...
4
votes
3answers
263 views

Mathematical Induction proof for a cubic equation.

If $ x^3 = x +1$, prove by induction that $ x^{3n} = a_{n}x + b_n + \frac {c_n}{x}$, where $a_1=1, b_1=1, c_1=0$ and $a_n = a_{n-1} + b_{n-1}, b_n = a_{n-1} + b_{n-1} + c_{n-1}, c_n = a_{n-1} + ...
2
votes
2answers
30 views

Need Help Understanding Algabraic Steps in an Inductive Proof

This question is about an inductive proof which was posted yesterday on this web site here: Proving $\frac{5\cdot3^{4n + 1} - 2^{2n}}{7}$ is an integer. This topic was put on hold as off topic. I'm ...
1
vote
3answers
243 views

Is there any commonality between Math induction and Logic induction?

Logic induction is reasoning by probability. Math induction seems to be related to just Natural numbers and used to prove a statement for every natural number. From these definitions there is no ...
0
votes
3answers
47 views

Proving ${\sum}^n _{i=1}i = \frac {n(n+1)}{2}$ by induction

I am having problems understanding how to 'prove' a summation formula. I have the equation: $ {\sum}^n _{i=1}i = \frac {n(n+1)}{2} $ Basis Step when: $ n=1 $ $ {\sum}^1 _{i=1}i = \frac ...
1
vote
4answers
86 views

Proving that the sum of the first $2n$ terms of the series $1^2 - 3^2 + 5^2 - \cdots$ is $-8n^2$ by induction

Use mathematical induction to prove the following for the first $2n$ terms of the series $$1^2 - 3^2 + 5^2 - 7^2 + \cdots = -8n^2.$$ As we have odd numbers that are squared we could use $n = ...
1
vote
3answers
84 views

I need a hint on a proof using mathematical induction

I'm trying to prove that $k^k+1\ge2^k$ using mathematical induction but i'm missing something. How can i establish the binomial $(k+1)^{k+1}$? As a first step, i multiplied both sides by $2$ and $k$ ...