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
vote
1answer
21 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
72 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
0answers
72 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
52 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
50 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
56 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
53 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
47 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
107 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
39 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
76 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
548 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
50 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
58 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
25 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 ...
-4
votes
0answers
46 views

prove that for any 2n≥2 and any \a ​1 ​​ ,…,a ​n ​​ ∈N, we have the following: [closed]

So the question I was given goes like this we will introduce a mystery function,P:N→N. We don't know a formula for P (and we won't be able to determine one!) but we do know that P satisfies the ...
1
vote
2answers
94 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
75 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
51 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
34 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
65 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}?$$
0
votes
1answer
39 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
65 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
39 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
53 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
251 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
188 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 ...
-2
votes
3answers
58 views

$2^n < (n+2)!,$ for $n \geq 0$ [closed]

Prove by induction I'm working on a self thought book but the solution isn't available. Can someone explain please?
1
vote
4answers
85 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 = ...
0
votes
3answers
80 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$ ...
1
vote
0answers
49 views

Is it possible to use induction to prove Laplace Expansion Theorem?

Laplace expansion theorem is used to find the determinant of an $n \times n$ matrix. It can be applied along a row or along a column. Let's assume that we can prove this theorem using induction (As it ...
0
votes
1answer
44 views

Induction question , 0 and 1's quesiton [duplicate]

$010$ can be generated. If $s$ is a sequence which can be generated by these rules, then $01s, 10s, 0s1, 1s0, s01$, and $s10$ can all be generated. *Prove, by induction, that in any sequence ...
2
votes
8answers
117 views

Prove by induction that $\frac{n^3}{3}+\frac{2n}{3}$ is an integer. [duplicate]

The question that I am working on is: Prove that $\dfrac{n^3}{3}+\dfrac{2n}{3} \in \mathbb Z \ \forall \ n \in \mathbb N$ The method that I think would be will work for this question is that I ...
0
votes
2answers
54 views

Induction question regarding Universe

I was given a question that looks like this. Prove that for each $2 \le n\in \mathbb N$, if $X_1,\ldots,X_n$ are subsets of some universe $U$, then the following is true: $$(X_1 \cup\cdots\cup ...
1
vote
3answers
68 views

Induction Proof using factorials

Recall that for $n \in N$, $n! = 1 \cdot 2 \cdots n$. Prove the following for each $n \in N$: $$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \cdots + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}$$ I ...
0
votes
4answers
77 views

Prove for each $n\in \mathbb{N}, 1^3 + 2^3 +\cdots+ n^3 = \frac{n^2(n+1)^2}{​4} ​ ​​​$ [duplicate]

So I was given a proof by induction question and here is my attempt $$1^3 + 2^3 + 3^3+\cdots+n^3= \frac{n^2(n+1)^2}{4}$$ $n=1$ $1=1$ Induction step: Assume statement is true for $n=k$, show true ...
0
votes
3answers
58 views

proof by induction $2^n \leq 2^{n+1}-2^{n−1}-1$

My question is prove by induction for all $n\in\mathbb{N}$, $2^n \leq 2 ^{n+1}-2^{n−1}-1$ My proof $1+2+3+4+....+2^n \leq 2^{n+1}-2^{n−1}-1$ Assume $n=1$,$1 ≤ 2$ Induction step Assume statement ...
2
votes
2answers
30 views

Strong Induction to prove $T(n)$ is $O(n)$ for $T(n) = T(\lfloor n/3 \rfloor) + T(\lfloor n/5 \rfloor) + T(\lfloor n/7 \rfloor) + n$

I have some questions about Strong Induction where the inductive procedure isn't entirely clear to me. I will use a specific example to demonstrate and present my attempt at a proof with questions ...
1
vote
5answers
61 views

Proof by induction that $3^{2n} + 7$ is divisible by $4$

Demonstrate by induction: $3^{2n} + 7 = 4k$ is true, for any $n\in \mathbb N$. I need to demonstrate this using the induction principle. So far I have: $n = 1$ $$3^{2\cdot 1} + 7 = 4\cdot k $$ $$9 ...
0
votes
4answers
43 views

Proof of Natural set to any power k, is countably infinite [duplicate]

Show that $N^k = N × N × \cdots × N$ ($k$ factors) is countably infinite for every positive integer $k$. where $N$ is the set of natural numbers. I first approached this question by trying ...
0
votes
1answer
61 views

Finding the error in this induction proof [duplicate]

Claim: If $n$ belongs to $\mathbb{N}$, and $p$ and $q$ are natural numbers with maximum $n$, then $p=q$. Let $S$ be the subset of the natural numbers for which the claim is true. $1$ belongs to $S$, ...
0
votes
1answer
102 views

Induction, 0'1 and 1's sequence fun question [closed]

010 can we generated. If s is a sequence which can be generated by these rules, then 01s, 10s, 0s1, 1s0, s01, and s10 can all be generated. -Prove (by induction?!) that in any sequence generated by ...
2
votes
1answer
54 views

INDUCTION: Let a sequence of numbers $a_n$ for $n\in \mathbb N$ be defined by the following rule: $a_1 = 1$, and for $n>1$, $a_n = 2a_{n-1} + 1$

Prove that $a_n = 2^n - 1$ for all $n\in\mathbb N$. I don't see how the sub n and n to the power of anything can correlate. I'm missing something for I've been staring at the combinations I tried to ...
3
votes
0answers
19 views

Proof of Leibniz formula from Laplace expansion

I'm trying to prove Leibniz formula for the determinant using Laplace expansion. Here's my attempt: For a $1 \times 1$ matrix $A = \begin{pmatrix}a_{11}\end{pmatrix}$, define $\det A = a_{11}$. For ...
1
vote
1answer
17 views

Using induction to prova a regular expression belongs to the language generated by a grammar (well half-proving anyways)

I have a grammar with this productions S->aBSBBa |$ \epsilon $ B->bB|$\epsilon$ $L(B)=b^*$ (by Arden's rule) and seems that $L(S) = a(b+ab^*a)^*a + \epsilon$ I have to prove that last ...