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

3
votes
4answers
98 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
37 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
54 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
510 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
43 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
56 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
23 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
43 views

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

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
73 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
79 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
48 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
109 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
33 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
64 views

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

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
36 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
61 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
38 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
244 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 ...
-2
votes
2answers
27 views

Induction problem [closed]

Fibonacci sequence $f_0 = 1~~ f_1=1$ and for every $n >=2 ~~ f_n= f_{n-1} + f_{n-2}$. Prove for all $n >=0$, $f_n <= 2^n$. Currently working on a self taught book but this problem doesn't ...
1
vote
3answers
156 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
46 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
votes
3answers
51 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
41 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 ...
-4
votes
1answer
65 views

Prove that $D = \{3n: n \in \mathbb{Z}^+ \}$ [closed]

Let $D$ be the set whose members are defined as follows: Basis Step: The number $3 \in D$. Recursive Step: If $x \in D$ and $y \in D$, then $x + y \in D$. Prove that $ \{3n: n \in \mathbb{Z}^+ \} ...
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
53 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
73 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
57 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
59 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
101 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 ...
2
votes
0answers
17 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 ...
-2
votes
2answers
75 views

general formula using informal inductive reasoning

if I have 4 equations.. $$ 1=1$$ $$2+3+4=1+8$$ $$5+6+7+8+9=8+27$$ $$10+11+12+13+14+15+16=27+64$$ how do I find the general formula (that is suggested by the equations) using informal inductive ...
4
votes
2answers
93 views

Prove by induction that $4$ divides $n^3+(n+1)^3+(n+2)^3+(n+3)^3$

Just looking for someone to check my work and for feedback, thanks! Base case: $n=0$ $0+1+8+27 = 36$ $4$ divides $36.$ Inductive step: Assume $4$ divides $k^3+(k+1)^3+(k+2)^3+(k+3)^3$ for some ...
0
votes
0answers
22 views

Can the axiom of induction be replaced by simpler axioms from which it could be deduced and proved? [duplicate]

Can the axiom of induction be replaced by simpler axioms from which it could be deduced and proved? If that's possible does it require significant changes to the other peano axioms?
0
votes
1answer
46 views

Constructive Induction to derive and prove the formula for a geometric sequence

$\sum_{i=1}^nr^i = a \cdot (b^n) + c$ Base Case: n=1, this holds Inductive Hypothesis: Assume for $n = k$, $k \ge 1$ that $\sum_{i=1}^k r^i = a * (b^k) + c$. Inductive Step: Prove for $n = k+1$ ...
2
votes
0answers
17 views

How to find variance of k+1 elements if variance of k elements is known?

I need to find the variance of k+1 elements given the variance of k elements. I can also store other features for k elements like mean ($\mu_n$) etc. So, given the below function's value, $$ ...
1
vote
2answers
39 views

How do I write $2(2^k+1) - 1$ as $(2 \cdot 2^k + 1)$?

How do I write $2(2^k+1) - 1$ as $(2 \cdot 2^k + 1)$? Mathematically, it is equivalent. But I need to the former form into the latter form for step 2 of inductive step for mathematical induction ...
2
votes
1answer
57 views

Is there a general rule for how to pick the base case value for proofs by mathematical induction?

I was looking at how to do mathematical induction. One source said to use $n = 1$ for the basis step. But I have seen other sources choose the value $n = 0$. So the question is as follows: ...