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
4answers
54 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
17 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
votes
0answers
25 views

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

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
93 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
69 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
78 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
46 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
106 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
62 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
35 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
59 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
242 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 [on hold]

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
149 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
45 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
49 views

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

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
33 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
116 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
72 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
28 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
73 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
38 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
55 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: ...
2
votes
3answers
58 views

Proving $n \lt 2^n$ for $n\geq 1$ using induction

Very close to understanding this, hopefully. Via induction, I'm following a proof but can't understand one of the last steps. Claim: $n < 2^n$ for natural numbers $n = 1, 2, 3,\ldots$ For step ...
0
votes
3answers
62 views

Induction Inequality with Summation [closed]

I can't seem to figure out this problem. Do you have any ideas? For an integer $n > 1$, show that $$ \sum_{k=1}^n {1\over \sqrt{{n^2}+k}} > {{\sqrt{1+{1\over n}}}\over 2} $$
-1
votes
3answers
70 views

Show that ${n\choose k}\leq 2^n$

Show that ${n\choose k}\leq 2^n$ for all naturals with $0\leq k \leq n $.I know I need to use induction and for the base case $n=1$ what exactly am I showing?
-1
votes
3answers
63 views

Prove the inequality by induction [duplicate]

Prove the inequality by induction: $3^n > n^3\ $ for $\ n \geq 4$ Edit: 1) Base case: $n=4$, $3^4>4^3, 81>64$ 2) Assume true for n=k: so $3^k>k^3$ 3) Consider $(k+1)^3$, $(k+1)^3 = ...
0
votes
1answer
55 views

strong induction case

im stuck on this assignment. Can someone give me a hint? Here is the assignment: There are two types of creature on planet Char, Z-lings and B-lings. Furthermore, every creature belongs to a ...