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

0
votes
2answers
35 views

Matrices proof by induction

For any 3x3 matrix $A$, prove by induction that $$(A^T)^n=(A^n)^T$$ for all $n∈ℕ$ I'm not sure how I do this.
1
vote
1answer
50 views

Math Induction $N$ greater than or equal to $2$

$(1-\frac{1}{2})$$(1-\frac{2}{3})$$(1-\frac{1}{4})$...$(1-\frac{1}{n})$=$(\frac{1}{n})$ So I'm trying to make it equal. so $n$ is equal or greater than 2. When i substitute $2$ to n, $(1-\frac{1}{2})$...
1
vote
1answer
31 views

Stirling Numbers of the First Kind Proof

Prove the following: $$\sum\limits_{k=0}^{r}|s(n,k)| = n! - \sum\limits_{k=0}^{n} - |s(n,k+r+1)|$$ Workings: Proof: Base case: $n = 0, r = 0$ $s(0,0) = 1$ $0! - s(0,0+0+1) = 1 - 0 = 1$ Base ...
0
votes
2answers
45 views

Reverse inductive proof

This is probably a stupid question. Let us say I were to prove something by induction. Is it true, that the basecase must be the lowest possible number? If I wanted to prove that the formula holds ...
1
vote
2answers
86 views

Show by induction on $n$ that:

$$1^4 + 2^4 +\cdots+n^4=\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}$$ I proved true for case $n=1$ , assumed true for $n=k$ , but cannot get things to work out. I tried putting the right ...
0
votes
1answer
531 views

Show that $P_n=p(1-P_{n-1})+(1-p)P_{n-1}$ $n \ge 1$ [duplicate]

Independent trials that result in a success with probability p and a failure with probability 1-p are called Bernoulli trials. Let $P_n$ denote the probability that n Bernoulli trials result in an ...
2
votes
4answers
495 views

Inductive definition of power set for finite sets

I'm stuck on a problem using recursive definitions: Let $X$ be a finite set. Give a recursive definition of the set of all subsets of $X$. Use Union as the operator in the definition. I can see ...
1
vote
1answer
94 views

Recursive Definition of Is Equal To

I'm working through some of the intro problems in Sudkamp's Languages and Machines (basically an intro book to finite automata, context free grammars, Turing machines, etc), and I'm struggling a bit ...
4
votes
6answers
202 views

Summation inductional proof: $\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\ldots+\frac{1}{n^2}<2$ [duplicate]

Having the following inequality $$\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\ldots+\frac{1}{n^2}<2$$ To prove it for all natural numbers is it enough to show that: $\frac{1}{(n+1)^2}-\frac{1}{n^2}...
5
votes
1answer
79 views

induction exercise - having struggles with $1^3 + 2^3 + … + (n+1)^3 = [(n(n+1))/2]^2$

I'm trying to solve by induction that $1^3 + 2^3 + ... + (n+1)^3 = [(n(n+1))/2]^2$ However, I have a lot of trouble, and it must be said that I don't do a great deal of mathematics. I keep getting ...
0
votes
2answers
55 views

Prove $(bab^{-1})^n = ba^nb^{-1}$ by induction

p(1): $(bab^{-1})^1 = ba^1b^{-1}.$ p(k + 1): $(bab^{-1})^{k + 1} = (bab^{-1})^k(bab^{-1}) = b^ka^kb^{-k}bab^{-1} = ba^{k + 1}b^{-1}.$ Would that work?
2
votes
1answer
188 views

Can the chain rule be proven by math induction?

I need to prove the chain rule for a math project and I am wondering if it can be proven by math induction. If not, how can this rule be proven?
0
votes
4answers
109 views

Induction proof: sum of binomial coefficients

Prove by mathematical induction for all natural numbers $n$: $$\sum_{k=0}^{n} \binom{n}{k}=2^n$$ thus is it sufficient to show that (but I think I made a mistake) thus how to do it properly? $$2^...
0
votes
3answers
85 views

Usage of Mathematical Induction

How do I prove this with Mathematical Induction? Whereby $$u_1, u_2...u_n$$ are all positive and are in an arithmetic progression for $$n\geq2$$ $$\sum\limits_{k=2}^{n}\frac{1}{(u_{k-1})\cdot(u_k)}=\...
15
votes
5answers
403 views

Proving $\frac{n^n}{e^{n-1}}<n!<\frac{(n+1)^{n+1}}{e^{n}}$ by induction for all $n> 2$.

I am trying to prove $$\frac{n^n}{e^{n-1}}<n!<\frac{(n+1)^{n+1}}{e^{n}} \text{ for all }n > 2.$$ Here is the original source (Problem 1B, on page 12 of PDF) Can this be proved by ...
3
votes
5answers
104 views

Induction exercise check-up

Prove by induction on $n$ that $13$ divides $2^{4n+2} + 3^{n+2}$ for all natural $n$. For base case it is divisble by 13, and $2^{4n+6} + 3^{n+3}$ must be divisble too. $16 * 2^{4n+2}+ 3* 3^{n+2}$ ...
0
votes
2answers
45 views

Mathematical induction final step — proving $n^3 \leq 2^n$, where $n\geq 10$

I was solving an induction exercise, but I got stuck here, and I'd like a hint ($n \geq 10$). Claim: $n^3 \leq 2^n$ I have that $3n^2 + 3n \leq 2^n - 1$, but I am unsure as to how to proceed.
1
vote
2answers
100 views

Proof by induction; inequality

Ok so I'm kind of struggling with this: The question is: "Use mathematical induction to prove that 1*3 + 2*4 + 3*5 + ··· + n(n + 2) ≥ (1/3)(n^3 + 5n) for n≥1" Okay, so P(1) is true as 1(1+2)=3 and (...
1
vote
1answer
78 views

Stirling Numbers of First Kind Proof by Induction

Prove the following by using a proof by industion: $$\sum\limits_{k=0}^{n} |s(n,k)| = n!$$ where $s(n,k)$ is the Stirling Numbers of the First Kind. Workings: Proof: The recurrence relation for $...
1
vote
1answer
53 views

Prove that $ exp_{a}(\frac{p}{q}) = \sqrt[q]{a^{p}} \space \forall \space p,q \in \mathbb{Z} $

Prove that $ exp_{a}(\frac{p}{q}) = \sqrt[q]{a^{p}} \space \forall \space p,q \in \mathbb{Z} $ with $ q \geq 2 $ I'm not sure how to approach this question. I was thinking through in induction with ...
0
votes
2answers
336 views

Proof by induction (combinations)

We are supposed to prove this via induction. I originally solved it with simple algebra, showing that $n = n$ and $n+1 = n+1$, but a friend told me that wasn't really solving it by induction and said ...
1
vote
2answers
651 views

Proof by induction and combinations

I think I am stuck on this, I am not sure if I'm going down the correct path or not. I am trying to algebraically manipulate $p(k+1)$ so I can use $p(k)$ but I am unable to do so, so I am not sure if ...
1
vote
1answer
35 views

Can induction be used for $n \leq 0 $

Example question Prove that $ exp(n) = e^{n} \space \space \forall \space n \in \mathbb{Z} $ First I prove by induction for $ n \geq 0 $ and then I do the same for $ n \leq 0 $ Is this allowed ?
0
votes
2answers
71 views

Question about induction to infinity with regard to Bolzano's philosophy

I'm a philosophy and mathematics student, and I'm writing a paper on a proof put forward by Bolzano that if we can know one thing to be true, then we can know infinite truths. Put simply, he states ...
3
votes
1answer
44 views

Proof: $2\sqrt{m}-2 < \sum\limits_{n=1}^m\frac{1}{\sqrt{n}}< 2\sqrt{m}-1$

I know that problems similar to this one, involving either one of the two bounds, have been posted before, but I would like just a hint in the last part of the proof involving the upper bound, with ...
0
votes
2answers
37 views

Induction. $\forall k\in \Bbb N , \sum^{2k-1}_{n=k}\frac{n}{2^n}=\frac{(2k+2)2^k-4k-2}{2^{2k}}$

$$\forall k\in \Bbb N , s_k=\sum^{2k-1}_{n=k}\frac{n}{2^n}$$ I have to show that : $$s_k=\frac{(2k+2)2^k-4k-2}{2^{2k}}$$I think that induction is needed there. I've checked that it's true for $k=1$ ...
2
votes
6answers
147 views

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

How can I show that $n^2<n!$ for all $n\geq 4$ Step 1 For $n=1$, the LHS=$4^2=16$ and RHS=$4!=24$. So LHS$<$ RHS. Step 2 Suppose the result be true for $n=k$ i.e., $k^2<k!$ Step 3 ...
21
votes
6answers
4k views

Why is mathematical induction a valid proof technique? [duplicate]

Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows. Problem: The main form for normal induction over ...
4
votes
2answers
111 views

Proof by Induction: $2(\sqrt{n+1} - \sqrt{n}) < \frac{1}{\sqrt{n}} < 2(\sqrt{n}-\sqrt{n-1})$

I'm having some troubles trying to prove the Exercise 13, page 41 of Apostol's Calculus I, which is the one used to explain some features of integration in the next pages. It says: Prove that $2(\...
1
vote
2answers
61 views

Proof by induction $n^2-2n-1>0$ for $n \ge 3$

I want to use induction to prove that $n^2-2n-1>0$ for $n \ge 3$ Base case: $3^2-2(3)-1>0$ $ \space \checkmark$ Inductive step: $(n+1)^2-2(n+1)-1>0$ $\iff n^2+2n+1-2n-2-1>0$ $\iff n^2-...
1
vote
1answer
69 views

Lucas Number Sequence

Can anyone help me in this question: Define $ (b_n)$ as $b_1= 1,b_n=a_{n+1} - a_n $ for $ n\ge 2$, where $ a_n $ is the Fibonnaci series. This sequence is known as the sequence of Lucas numbers. ...
0
votes
1answer
195 views

Prove by induction that every complete $k$-ary tree of depth $n$ has $(k^{n+1}–1)/(k-1)$ nodes for all integers $n\ge 0$, where $k\ge 2$.

A strictly $k$-ary tree is a $k$-ary tree (a binary tree is a $2$-ary tree) in which every node has either no children (is a leaf) or $k$ children. A complete $k$-ary tree of depth $n$ is a strictly $...
0
votes
1answer
52 views

Induction divisibility proof

Prove that $4^n \sum_{k=0}^{n} \binom nk +14n-1 $ is divisible by $7$ for every $n \geq 1$. Basic Step: For $n=1$, $21$ is divisible by $7$.($21 \mod 7 = 0$) Induction Hypothesis: Suppose that ...
1
vote
1answer
56 views

Trying to show a probability equation by induction

Suppose $A_1,...,A_n$ are events, then $$ P( \bigcup A_i ) = \sum_{i=1}^nP(A_i) - \sum_{i <j}P(A_i \cap A_j) + \sum_{i < j < k}P(A_i\cap A_j \cap A_k) - ... + (-1)^{n+1} P( \bigcap_i A_i) $$...
1
vote
1answer
55 views

Can someone make this question clear to me and give me a hint?

By using induction, prove that $s_{2^n} \geq 1 +n/2$ for all $n\in \mathbb N$, where $s_j=\sum\limits_{i=1}^j 1/i$ is the $j$-th partial sum of the Harmonic Series. Note that this implies the partial ...
1
vote
1answer
442 views

proving my induction in game theory doubt

Highly connected website problem Suppose we have n websites such that for every pair of websites A and B, either A has a link to B or B has a link to A. Prove by induction that there exists a website ...
4
votes
1answer
57 views

A reccurent sequence

Let $(a_n)$ a sequence such that: $a_1=1$ and $a_2=2$ and $a_3=3$ such that $a_n=\frac{a_{n-1}a_{n-2}+7}{a_{n-3}}$ show that $ a_n \in \mathbb{N} $ I tried to find a particular form of the sequence,...
3
votes
3answers
97 views

Prove that $n(n-1)<3^n$ for all $n≥2$ By induction

Prove that $n(n-1)<3^n$ for all $n≥2$. By induction. What I did: Step 1- Base case: Keep n=2 $2(2-1)<3^2$ $2<9$ Thus it holds. Step 2- Hypothesis: Assume: $k(k-1)<3^k$ Step 3- ...
0
votes
2answers
48 views

Prove that $n < 2^n$ for all n holds N.

Prove that $n < 2^n$ for all $n ∈ N$. By induction. I know how simple is this, but could anyone help and give detailed explanation? Edit: Its $2^n$ NOT 2n
4
votes
1answer
78 views

Fibonacci Numbers, show $F_n \ge 2^{n/2}$ for $n \ge 6$. [duplicate]

I want to show that for the Fibonacci numbers, $F_n$ $>=$ $2^{n/2}$ for n $>=$ 6. My thought was to prove this via induction. I showed the base case is true for $F_n$, n=6 and 7. I assumed ...
2
votes
3answers
65 views

Induction proof, greater than

Prove that: $n!>2^n$ for $n \ge 4$. So in my class we are learning about induction, and the difference between "weak" induction and "strong" induction (however I don't really understand how strong ...
5
votes
2answers
78 views

Induction proof that $1^3+2^3+…+n^3=\frac{n^2(n+1)^2}4$ [duplicate]

Prove that: $1^3+2^3+...+n^3=\frac{n^2(n+1)^2}{4}$ for $n \in N$ So I am thinking that I need to do a proof by mathematical induction. Here's my attempt: Let S(n) be the statement $1^3+2^3+...+n^3=\...
2
votes
3answers
80 views

Prove that $4^n > n^4$by induction for $n\ge 5$ [duplicate]

That is a simple question and I can't start a simple desenveloment. Just $k=5$ we have $4^5 = 1024 > 5^4 = 625$ for $k+1$: $4^{k+1} > (k+1)^4\Rightarrow 4^k > (k+1)^4/4$ And How can i ...
-1
votes
1answer
79 views

prove set definition - by induction?

$X\subseteq Z^+$ defined recursively as: $1)$ $3\in X$; and $2)$ If $a,b\in X$, then $a+b\in X$. Prove that $X=\{3k|k\in Z^+\},$ the set of all positive integers divisible by $3$. Induction on the ...
1
vote
2answers
64 views

Showing a sequence defined recursively is convergent

Given the recursively defined sequence $$ a_1 = 0, a_{n+1} = \frac 1{2+a^n} $$ Show it converges. I'm working with Cauchy sequences, and proved in a previous question that any sequence of real ...
1
vote
1answer
77 views

Proving the Fibonacci identity $\sum_{i=1}^n f_i^2=f_nf_{n+1}$ by induction [duplicate]

I am having troubles with a proof question. Prove that for any $n\ge1$, $\sum_{i=1}^n f_i^2=f_nf_{n+1}$, where $f_n$ is the $n$'th Fibonacci number. I have the base case and the induction ...
2
votes
3answers
150 views

Help Figuring Out Faulty Proof

In my discrete math class, we're working on faulty proofs. I can't seem to figure out why this proof is faulty. I think it has to due with them assuming $k^2 \le k^2 + 2k$. Anyone have any ideas? ...
2
votes
1answer
52 views

Rigor of this direct justification of mathematical induction

Proofs of a mathematical statement or theorem can have different levels of rigor and I have a question about this. In the method of mathematical induction, there are statements numbered with 1, 2, 3 ...
3
votes
4answers
75 views

Prove that $(n^2-1)\mid(n^3+1)$ iff $n=2$

Seperating $n^2-1$ into $(n+1)(n-1)$. I have noticed that $n^3+1=(n+1)(n^2-n+1)$, so we have $\forall n\geq 2$, $(n+1)\mid(n^3+1)$. We now need to show that $(n-1)\mid(n^2-n+1)$ iff $n=2$ This ...
1
vote
1answer
27 views

Proof of geometric sum relation by mathematical induction

I understand the concept behind mathematical induction and have worked out some examples before. However, this was given as a question on a homework assignment and I'm unable to work it out. I'm not ...