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
0answers
50 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
119 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
56 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
74 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 ...
1
vote
3answers
59 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
32 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
63 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
44 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
66 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
106 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
56 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
23 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
82 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
95 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
23 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
53 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
22 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
46 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
63 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
61 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
67 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
71 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
61 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 ...
0
votes
1answer
32 views

Proof by induction with the Union of sets

Proof by induction: $$ P( \cup _{i=1}^n A_i)=\sum_{i=1}^n P(A_i) - \sum_{1 \leq i_1 < i_2 \leq n} P(A_{i_1} \cap A _{i2} ) + \sum_{1 \leq i_1 < i_2 <i_3 \leq n} P(A_{i1} \cap A_{i2} \cap ...
1
vote
3answers
61 views

Mathematical Induction getting the right side

So I 've been doing Mathematical Inductions but I seem to have a issue in simplify and getting the right side. So I have this on the L.H.S $$\frac{k(k + 1)(2k +1)}{6} + (k + 1)^2 $$ And I'm trying ...
0
votes
1answer
36 views

Prove that $\sum_{k=1}^{n-1}k^{3}\leq \frac{n^{4}}{4}\leq \sum_{k=1}^{n}k^{3}$ for all $n\geq 2$.

Prove that $$\sum_{k=1}^{n-1}k^{3}\leq \frac{n^{4}}{4}\leq \sum_{k=1}^{n}k^{3}$$ for all $n\geq 2$. This is just a random exercise to improve my proof techniques. I want to show it by induction ...
4
votes
3answers
83 views

Proof of $\sum^{2N}_{n=1} \frac{(-1)^{n-1}}{n} = \sum^{N}_{n=1} \frac{1}{N+n}$

The title pretty much summarizes my question. I am trying to prove the following: $$\displaystyle \forall N \in \mathbb{N}: \sum^{2N}_{n=1} \frac{(-1)^{n-1}}{n} = \sum^{N}_{n=1} \frac{1}{N+n}.$$ I ...
4
votes
3answers
66 views

Show that $\frac{1\cdot 3\cdot 5\cdot \ldots \cdot (2n-1)}{1\cdot 2\cdot 3\cdot \ldots \cdot n}\leq 2^{n}$ for all $n\in\mathbb{N}$.

Show that $$\frac{1\cdot 3\cdot 5\cdot \ldots \cdot (2n-1)}{1\cdot 2\cdot 3\cdot \ldots \cdot n}\leq 2^{n}\qquad (n\in \mathbb{N}).$$ I want to show the last step, that is, the inductive step. ...
8
votes
2answers
226 views

Real Induction Over Multiple Variables?

I've seen in several different places* that one can use normal mathematical induction to prove the truth of a statement that relies not on just one variable (say, $x$,) but multiple variables (for ...
4
votes
3answers
62 views

Induction proofs for subsets of integers

I know that induction can be used to prove that certain results hold true for all integers, all positive integers, all negative integers, all rational numbers and so on. What I'm noticing from listing ...
2
votes
2answers
36 views

Proofs: Induction on Handsakes

Here is the problem: Suppose $n$ people are at a party, and some number of them shake hands. At the end of the party, each guest $G_i$, $1 \leq i \leq n$ shares that they shook hands $x_i$ times. ...
0
votes
0answers
54 views

Transition matrix proof

Let $P=\begin{bmatrix}1-a&a\\b&1-b\end{bmatrix}$, with $0<a,b<1$. Show that ...
0
votes
0answers
52 views

How do I solve Exercise 6.2.4 (a) of 'How to Prove It' by Velleman?

I spent 6 hours on it, and I couldn't wrap my head around it. The problem is described below. I am stuck on Case 2. 6.2.4. (a) Suppose R is a relation on A, and ∀x∈A∀y∈A(xRy ∨ yRx). (Note that this ...
0
votes
3answers
77 views

Prove the laws of exponents by induction

We inductively define $a^1=a, a^{n+1}=a^n a$. I want to show that $a^{n+m}=a^n a^m$. By definition, this is true if $m=1$. Now for $m=2$, we have $$ \begin{align} a^{n+2} =& a^{(n+1)+1}\\ ...
-1
votes
1answer
83 views

Strong induction different assumptions

I have a question regarding strong induction. I've seen examples on proofs that assume that P(n) is true for all n that is smaller or equal than k and thereby dealing with k+1 in the inductive step ...
0
votes
3answers
37 views

Given two specific sets, show that one is a subset of another

Given $$X = \{x : x = 4^n-3n-1 ; n\in\mathbb{N}\}$$ and $$Y = \{y : y = 9(n-1); n\in\mathbb{N}\}$$ Prove that $X \subset Y$. I've been struggling with this problem for hours but I couldn't find a ...
1
vote
1answer
44 views

Proving property of group-like algebraic structures by means of induction

How do you prove (by means of induction) that the following is true for all group-like algebraic structures? $$\operatorname{ord}(a_1 \circ a_2 \circ a_3 \circ \cdots \circ a_{n-1} \circ a_n) = ...
1
vote
0answers
27 views

The pencils in a box of crayons always have the same color [duplicate]

I retrieved an old math book and I'm delighted to share following exercise. The pencils in a box of crayons always have the same color. Proof by induction on the number $n$ of pencils in the ...
1
vote
1answer
20 views

More detailed explanation of how $2N_{h-2}$ becomes $2^{h/2}$?

I'm trying to learn the proof of the minimum number of nodes in an AVL tree of height h and I'm stumped on how $2N_{h-2}$ becomes $2^{h/2}$. I've read this [answer](How does $2N_{h-2}$ become ...
1
vote
2answers
34 views

Prove that $\tan \left ( \sum_{k=1}^{n} \theta_k \right ) \geq \sum_{k=1}^{n} \tan (\theta_k)$

I'm trying to prove by induction that $$\tan \left ( \sum_{k=1}^{n} \theta_k \right ) \geq \sum_{k=1}^{n} \tan (\theta_k)$$ provided that $$\sum_{k=1}^{n} \theta_k < \frac{\pi}{2}$$ So in ...
3
votes
3answers
71 views

Basic mathematical induction regarding inequalities

These are just the examples from my textbook, but I don't think it did not explain well. One of the problem was to prove the inequality $$n<2^n$$ for all integers $n$. I understand we assume ...
0
votes
2answers
47 views

Proving a Recursive Formula

I know there are some questions on this site about how to find a recursive formula, but I've already found the formula. I'm doing an assignment (http://mathstat.dal.ca/~svenjah/math2112/Assign6.pdf) ...
0
votes
0answers
46 views

Principle of infinite descent

I'm trying to prove the following: "It is not possible to have a sequence of natural numbers which is in infinite descent. (Hint: assume for sake of contradiction that you can find a sequence of ...
2
votes
2answers
70 views

Number Theory- Mathematical Proof

I am trying to prove a theorem in my textbook using another theorem. What I need to show that if a,b, and c are positive integers, show that the least positive integer linear combination of a and b ...
3
votes
1answer
46 views

Prove equality of Fibonacci sequence

Let $u(n)$ — the Fibonacci sequence. Prove that $$u(1)^3+...+u(n)^3=\frac{ 1 }{ 10 } \left[ u(3n+2)+(-1)^{n+1}6u(n-1)+5 \right].$$ I suppose we need prove that equality by iduction in $n$. ...
0
votes
1answer
57 views

A proof by induction and trigonometry

Do you know how to prove that $cos(\frac{X}{2}) + cos(\frac{3x}{2})... + \frac{cos(2n-1)}{2} = \frac{sin(nx)}{(2sin1/2x)}$ with induction? I have tried with n = 1 which gives $cos \frac{x}{2} = ...
1
vote
1answer
56 views

Lines in the plane from Concrete Mathematics. How many bounded regions are there?

I'm studying Concrete Mathematics by Donald Knuth. While doing the warmup questions, from the recurrence chapter, I stumbled upon an interesting problem. I have an intuition about the solution but I ...