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
72 views

Proof of $2^n \ge n^2 $ for $n \ge 4 $

I am currently learning induction and I understand the proof except the last line: $$ 2^{n+1} \ge (n+1)^2$$ I'm aware of the fact that, at some point (here $n=4$) an exponential function grows ...
1
vote
3answers
112 views

Find a closed form for the equations $1^3 = 1$, $2^3 = 3 + 5$, $3^3 = 7 + 9 + 11$

This is the assignment I have: Find a closed form for the equations $1^3 = 1$ $2^3 = 3+5$ $3^3 = 7+9+11$ $4^3 = 13+15+17+19$ $5^3 = 21+23+25+27+29$ $...$ Hints. ...
4
votes
1answer
44 views

Show that $n^3 > (n+1)^2$ for $n>2$ using mathematical induction

Is the following a correct way of showing that $n^3 > (n+1)^2$ for $n>2$ using mathematical induction? Thank you in advance! $P(n): n^3>(n+1)^2$ $P(3): 3^3>(3+1)^2$ $27 > 16$ ...
1
vote
2answers
86 views

Using mathematical induction to prove $\frac{1}1+\frac{1}4+\frac{1}9+\cdots+\frac{1}{n^2}<\frac{4n}{2n+1}$

This induction problem is giving me a pretty hard time: $$\frac{1}1+\frac{1}4+\frac{1}9+\cdots+\frac{1}{n^2}<\frac{4n}{2n+1}$$ I am struggling because my math teacher explained us that in ...
2
votes
1answer
37 views

Use induction to prove $\sum_{k=1}^n\frac{k}{2^k}=2-\frac{n+2}{2^n}$

Use induction on $n\in\Bbb N$ to prove that $$\sum_{k=1}^n\frac{k}{2^k}=2-\frac{n+2}{2^n}\;.$$ I have got as far as to the induction step where I have: $$S(n+1)= 2-\frac{n+3}{2^{n+1}}$$ and this ...
10
votes
2answers
139 views

There are 3 Zero-Sum Numbers!

Prove that for any set of $2n+3$ integers from the interval $[-2n-1,2n+1]$ there is a triple $(x,y,z)$ such that $x+y+z=0$. Example : Choose 5 number from {-3,-2,-1,0,1,2,3} there are x,y,z with ...
1
vote
1answer
89 views

Induction of closed form of summation

On Wikipedia the following closed form is derived - Generalised formula Can someone explain how the closed form below is derived? Edit Solution thanks to graydad
0
votes
1answer
167 views

King Arthur and knights at the round table puzzle

Can you help me with this math problem : Each of the $K$ knights from the round table needs to choose a card which is marked with a number from $1$ to $N$, $N \ge K$. The cards all have a different ...
0
votes
1answer
153 views

Use mathematical induction to prove that any integer n>=2 is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes. I know the steps of weak mathematical induction... basis step= $p(n)$ for $n=1$ or any ...
13
votes
5answers
279 views

How to prove $n < \left(1+\frac{1}{\sqrt{n}}\right)^n$

I want to know how to prove the following inequality. For $n = 1, 2, 3, \ldots $ $$ n < \left(1+\frac{1}{\sqrt{n}} \right)^n $$ I tried with math induction but I failed.
0
votes
3answers
61 views

Proof by minimum counter example

I need to prove that $n^4-n^2$ is divisible by 12 by minimum counter example. I understand the process but I don't understand how we arrive at m>=7. I have seen different proofs but I still don't know ...
2
votes
2answers
35 views

Proof by induction for $ \sum_{n}^{M} \cos(2n) = \frac{\sin(M) \cos(M+1)}{\sin(1)} $

Can someone show me an induction for $$ \sum_{n}^{M} \cos(2n) = \frac{\sin(M) \cos(M+1)}{\sin(1)} $$? My problem is doing that induction with $M$, I am not sure how to proceed to get the right side of ...
3
votes
3answers
93 views

prove by induction that $29^n - 21^n$ is always divisible by $8$

I have to prove by induction that that $\forall n \in N,$ $8 | (29^n - 21^n) $ . I understand how to prove things with induction generally, but im not sure where to even start with this one. I ...
0
votes
2answers
52 views

Proof using Induction

Give the induction proof of: $$ k(k+5) = \frac{k}{5} $$ Is this proof even possible? Not sure how to do.
1
vote
1answer
49 views

Proving Cauchy-Schwarz related proof using induction

So the first thing I was asked to prove was this: If $a_1,a_2,...,a_n$ and $b_a,b_2,...,b_n$ are real numbers, use induction to show. ...
3
votes
0answers
103 views

Prove, using the method of mathematical induction that the following holds true

For natural numbers $n\ge1$ show the following inequality using induction. $$n^{1/n}\le 1+\sqrt{\frac{2}{n}}$$
0
votes
1answer
193 views

Proving number of edges in F = n - k

So if we let F = (V,E) be a forest with n vertices and k connected components (trees), how can I prove that the number of edges in F = n - k ? I was thinking of using induction, but I'm super lost. ...
3
votes
2answers
71 views

Show that it is the solution of the recurrence

I have to show that the solution of the recurrence $$X(1)=1, X(n)=\sum_{i=1}^{n-1}X(i)X(n-i), \text{ for } n>1$$ is $$X(n+1)=\frac{1}{n+1} \binom{2n}{n}$$ I used induction to show that. I have ...
4
votes
5answers
100 views

Prove that $F(1) + F(3) + F(5) + … + F(2n-1) = F(2n)$

(These are Fibonacci numbers; $f(1) = 0$, $f(3) = 1$, $f(5) = 5$, etc.) I'm having trouble proving this with induction, I know how to prove the base case and present the induction hypothesis but I'm ...
1
vote
1answer
33 views

Looking for a way to improve my inductive proof of a statement derived by Rolle's Theorem

The following problem is 'absolutely' clear: Problem: Let $f$ be continuous on the interval $[a,b]$ and $n$-times differentiable on $(a,b)$ and $f$ vanishes on $n+1$ points $x_0< x_1 < \dots ...
1
vote
0answers
28 views

Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

Proof by induction. For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown ...
1
vote
1answer
58 views

Inequalities - proof by induction

Proof by induction involving inequalities completely escapes me. I've encountered the following problem: For which non-negative integers n is $n^2 ≤ n!$? Prove your answer (by induction). So, ...
1
vote
4answers
91 views

Using mathematical induction to show that for any $n\ge$ 2 then $\prod_{i=2}^n\bigl(1-\frac{1}{i^2}\bigr)=\binom{n+1}{2 \cdot n}$

I'm trying to work through some practice problems but I've been stuck on this for god knows how long now and I've no idea where to even start. Just wondering if it would be possible for someone to ...
1
vote
1answer
80 views

Induction Proof that $\sum_{i=0}^n 3^{n-i} {n \choose i} = \sum_{i=0}^n (-1)^i 5^{n-i} {n \choose i}$

Show that for all $n\geq0$ $$\binom{n}{0}3^n+\binom{n}{1}3^{n-1}+\dotsc+ \binom{n}{n-1}3^{1}+\binom{n}{n} $$ $$= \binom{n}{0}5^n-\binom{n}{1}5^{n-1}+\binom{n}{2}5^{n-2}-\binom{n}{3}5^{n-3}+\dotsc ...
0
votes
3answers
91 views

Prove that $(1+2+3+\cdots + n)^2 = 1^3+2^3+3^3+\cdots + n^3$ for every $n \in \mathbb{N}$ [duplicate]

Prove that $(1+2+3+\cdots + n)^2 = 1^3+2^3+3^3+\cdots + n^3$ for every $n \in \mathbb{N}$. Proof. We will use mathematical induction. If $n = 1$, then we have $(1)^2= 1^3 = 1$. We must show that ...
2
votes
3answers
62 views

Induction Proofs - Mathematics

How do I show by mathematical induction that $2$ divides $n^2 - n$ for all $n$ belonging to the set of Natural Numbers
3
votes
3answers
83 views

How to prove $0 < a_n < 1$ by induction

I know $n \in \mathbb{N}$ and... $$ a_n = \begin{cases} 0 & \text{ if } n = 0 \\ a_{n-1}^{2} + \frac{1}{4} & \text{ if } n > 0 \end{cases} $$ Base Case: $$a_1 = ...
1
vote
1answer
30 views

Showing that a sequence (defined in terms of the previous sequence term) is increasing and bounded above

I'm stuck on this problem and I was wondering if you would be kind enough to help. The question follows: Let $x_{1} = 1$ and $x_{n}$ = $\sqrt{ 1 + 2x_{n-1}}$ for n $\geq$ 2. Show that the sequence ...
1
vote
3answers
40 views

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$ Should I prove this by induction? If so, how should I go about it?
5
votes
4answers
69 views

Prove that $ \frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!}+\cdots + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}$ for $n\in \mathbb N$

I want to prove that if $n \in \mathbb N$ then $$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!}+ \cdots+ \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}.$$ I think I am stuck on two fronts. First, I don't know ...
1
vote
1answer
73 views

Induction proof for Fibonacci numbers

I am trying to get a hang on the induction method for proof, but I'm still dubious of many aspect of this proof regarding its application to sequences of integers, such as the Fibonacci sequence. ...
0
votes
2answers
80 views

Prove sum of combinations

Let n and r be positive integers with n ≥ r. Prove that C(r, r) + C(r + 1, r) + ... + C(n, r) = C(n + 1, r + 1) I would like to approach with mathematical induction. However, I don't understand what ...
2
votes
3answers
127 views

How to prove this statement: $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that Still a beginner here. Need to learn formatting. I am guessing by induction? Not sure what or how to go forward with this. Need help ...
2
votes
4answers
75 views

Proving this $F_{n+1} \cdot F_{n-1} - F^2_n = (-1)^n$ by induction

Where $n \in \mathbb{N}$ and $$ F_n = \begin{cases} 0 & \text{ if } n = 0 \\ 1 & \text{ if } n = 1 \\ F_{n-1} + F_{n-2} & \text{ if } n > 1 ...
0
votes
4answers
51 views

Prove $H_{2^m} \leq 1 + m$, where $H_n = \sum\limits_{k=1}^n \frac{1}{k}$

I really I am not seeing how to continue my approach, which is this. Base case: $m = 1$, so we have $H_2 \leq 2$, where $H_2 = \sum\limits_{k=1}^2 \frac{1}{k} = \frac{1}{1} + \frac{1}{2} = ...
2
votes
4answers
266 views

Equilateral triangle is cut in $4^n$ congruent equilateral smaller triangles

I have an assignment on proof by induction: Suppose n is a positive integer. An equilateral triangle is cut into $4^n$ congruent equilateral triangles, and one corner is removed. (Figure 1 ...
0
votes
1answer
81 views

Strong induction on a sequence, proving two functions are equal?

Excuse the poor title, but my understanding is still a little fuzzy. Admins feel free to change it Here is the question from the book. suppose that $f_{0}, f_{1}, f_{2}...$ is a sequence defined ...
2
votes
1answer
39 views

Induction proof with inequalities

Consider the following claim: $$5^n > 4^n + 3^n + 2^n$$ (a) For what natural numbers is this claim true? (b) Prove that your answer to (a) is correct using induction on n.
0
votes
1answer
16 views

Lining a rectangular building square panels

I've been working on this for what feels like a lifetime now and I'm just not getting anywhere with it. I'm wondering if someone would be able to explain how to solve it for me? There is a ...
0
votes
3answers
41 views

By induction, show that for ∀n∈N, it is true that: [duplicate]

$$\sum_{i=1}^n 2^i=2+2^2+2^3+.....+ 2^n=2(2^{n}-1)$$ Any help/explanations would be REALLY appreciated. Also in the same vein: By induction, show that $$∀n∈\mathbb N: 11^{n+2} + 12^{2n+1}$$ is ...
2
votes
0answers
27 views

Confusion on particular step in this weak induction proof

I am studying for a midterm, and I came across this proof. Use mathematical induction(weak) to show that for all integers n $\geq$ 2 , if x$_{1}$, x$_{2}$, ... x$_{n}$ are strictly between 0 and 1 ...
0
votes
1answer
21 views

An induction proof in a set.

I have an induction problem that I have no idea how to start. So the question goes like this. Let $x_1=1$, $x_2=2$ and $x_n=x_{n-1} + 2x_{n-2}$. Prove that $x_n=2^{n-1}$ for all $n$ in the natural ...
1
vote
1answer
81 views

What sets does $\mathbb{N}$ include?

My text states that the set $\{1, 2, 3...\}$, and the set $\{101, 102, 103, 104...\}$ are elements of $\mathbb{N}$. Doesn't this imply that $\mathbb{N}=\{1, 2, 3... 101, 102, 103, 104...\{1, 2, 3 ...
0
votes
1answer
32 views

induction with factorials

I need help with this please. I understand step one is to let $n=1$. step two let $ n = k$. Step three prove for $k+1$. But I would like a clear example of each... Prove $$\sum_{i=1}^n ...
1
vote
1answer
44 views

Induction of factorial

I was perusing the wikipedia page on Mathematical induction, and it mentions it's possible to prove by induction that. $\frac{n^{n}}{3^{n}}<n!<\frac{n^{n}}{2^{n}}$ for $n\geq6$ Proof for $n=6$ ...
0
votes
4answers
54 views

Use strong induction to prove that n$\leq$3$^{n/3}$ for every integer n$\geq$0

Use strong induction to prove that n$\leq$3$^{n/3}$ for every integer n$\geq$0. According to steps of Strong Induction, 1) I assume the predicate as P(n): n$\leq$3$^{n/3}$ for every integer ...
2
votes
1answer
79 views

Structural Induction, Propostitonal formulae problem

I am kind of overwhelmed by this question. Can anyone give me some hints about where to start? Propositional formulae PF are inductively defined over the Boolean constants B := {1, 0} (true and ...
1
vote
1answer
41 views

Proof by induction of whole numbers

A sequence $X_1, X_2,\dots,X_n$ is defined by: $X_1 = 1$ and $X_{k+1} = \dfrac{X_k}{X_k + 2}$ for $k\ge1$. Show by using induction that $X_n = \dfrac1{2^n - 1}$ for all $n\ge1$. So far I've showed ...
1
vote
2answers
85 views

Proving a combinatorics equality

How to prove the following? Should I use induction or something else? Let n and r be positive integers with n ≥ r. Prove that $${\binom{r}{r}} + {\binom{r+1}{r}} + · · · + {\binom{n}{r}} = ...
0
votes
2answers
33 views

A pair of questions about isomorphism between two posets.

Theorem: Let $P = (X, \le)$ be a finite total order containing n elements. Let $Q = (\{1, 2, \ldots , n\}, \le')$. Then $P \cong Q$. I have a few questions about the proof of this theorem. In my ...