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
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$$ ...
15
votes
5answers
382 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
96 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
75 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
306 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
604 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
70 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
43 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
144 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
108 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 ...
1
vote
2answers
59 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 ...
1
vote
1answer
67 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
175 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 ...
0
votes
1answer
50 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
54 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
423 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 ...
3
votes
3answers
94 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
47 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
67 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
77 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 ...
2
votes
3answers
76 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
78 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
62 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
74 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
144 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
51 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
74 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
25 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 ...
1
vote
2answers
183 views

Divisibility Proof with Induction - Stuck on Induction Step

I'm working on a problem that's given me the run around for about a weekend. The statement: For all $m$ greater than or equal to $2$ and for all $n$ greater than or equal to $0$, $m - 1$ divides $m^n ...
0
votes
2answers
68 views

Proof by induction: Matrices

Given the matrix $A=\begin{pmatrix} 1 & 2 \\ 0 & 1\end{pmatrix}$, I want to prove that $A^k = \begin{pmatrix}1 & 2k \\ 0 & 1 \end{pmatrix}$ (=induction hypothesis). Since I struggled a ...
3
votes
1answer
65 views

Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$

Question: Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$ I know that it is possible to solve by factoring $n^3+1$ and showing that $n+1$ is a multiple, but I would like to show this via ...
1
vote
0answers
45 views

How do I solve this recurrence relation and prove by induction? [closed]

I have this summation formula: $T(n)=\sum_{i = 1}^{n}T(n-i)T(i-1)$. Base case is $T(0)=1$, $T(1)=1$. How do I find the recurrence relation and prove it by induction?
3
votes
1answer
95 views

Recursive Alegbraic Equation for binary trees? [duplicate]

Consider the number $b_h$ of binary trees of height $h$, where height is being measured by the number of levels. An empty tree has height $0$, a single node binary tree has height $1$, and there ...
3
votes
2answers
58 views

Use Induction to prove $\forall m,n \in \Bbb Z_{\ge 0}, 1 +mn \leq (1 + m)^n$

Use Induction to prove: $$\forall m,n \in N, 1 +mn \leq (1 + m)^n$$ for integers $m,n\ge 0$. My biggest problem with this proof is ...
1
vote
1answer
1k views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
6
votes
2answers
105 views

Proof by induction: $(1+x)^n > 1 + nx+nx^2$

This is one of the exercises that appears in Apostol's Calculus I. I'm not sure whether what I did is correct. Let $n_1$ be the smallest positive integer $n$ for which the inequality $(1+x)^n > 1 ...
1
vote
1answer
32 views

Difference Operators

Let $K$ be a field. Given a map $f\colon K\longrightarrow K$, and $h\not=0$ define $\Delta_h f$ to be the map $x\longmapsto\dfrac{f(x+h)-f(x)}{h}$. Then $\Delta_h^j f$ is defined for $j=0,1,2,\dots$. ...
0
votes
3answers
77 views

Does Induction theorem fails here at Euler's conjecture?

I read in a Book written by Raymond A. Barnett and Micheal R. Ziegler the way to prove conjectures for infinite members of a given set and that is, Mathematical Induction. When I read Induction, I ...
1
vote
2answers
40 views

Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$ Basis: $a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$ $a_2 = 2^2 + 1 = 4 + 1 = 5$ ...
5
votes
5answers
67 views

Demonstration of sum of powers of $2$ [duplicate]

Theorem : For every natural number $p$: $$\sum^p_{i=0} 2^i = 2^{p+1}-1$$ I trieed to demonstrate the theorem using induction Demonstration : $1)$ If we have $p=0$ then we get $2^0=2^{0+1}-1$ that is ...
4
votes
4answers
230 views

Proving a Statement using Mathematical Induction

I'm trying to prove that $6 \mid (n^3 - n)$ where $n$ is a nonnegative integer. I started off by proving the basic step with $P(6)=4$. The next step would be the induction. However I'm having a bit f ...