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
1answer
25 views

$a_1=2$ and $a_{n+1}=2+\frac{1}{a_n}\implies |a_{n+1}-a_n|\leq\frac14|a_{n-1}-a_n|$

Let $(a_n)_{n\in\mathbb{N}}$ satisfy that $a_1=2$ and $a_{n+1}=2+\frac{1}{a_n}$. Show that for all $n\in\mathbb{N}$ with $n\geq 2$, $$ |a_{n+1}-a_n|\leq\frac14|a_{n-1}-a_n| $$ So I can show ...
3
votes
3answers
3k views

Proving that $|xy| = |x| + |y|$ being $x$ and $y$ two strings

I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$: $$ |xy| = |x| + |y| $$ with $x, y \in \Sigma^*$. To ...
0
votes
2answers
35 views

Prove by induction fibonacci variation

Prove by induction: The fibonacci sequence is defined as follows: $f_1 = 1$, $f_2 = 1$ and $f_{n+2} = f_n + f_{n+1}$ for $n \geq 1$ Prove by induction that $f_1^2 + f_2^2 + \dotsb + f_n^2 = f_n ...
2
votes
3answers
88 views

$x+1/x$ an integer implies $x^n+1/x^n$ an integer

Suppose that $0\neq x\in\mathbb{R}$ and $x + \frac1x\in\mathbb{Z}$. Prove that, for all $n\ge1$, $x^n + \frac1{x^n}\in\mathbb{Z}$. I can't figure out and understand the question. Can you give me ...
1
vote
1answer
27 views

Find a closed form

How do I prove (with strong induction) that every positive integer $n$ has a representation in the form $$n = c_r2^r + c_{r−1}2^{r−1} + \cdots + c_2 2^2 + c_1 2 + c_0$$ where $r$ is a nonnegative ...
1
vote
3answers
111 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. ...
1
vote
0answers
51 views

Closed form of an equation

How could I 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 ... and Prove this closed form by induction? Thanks
0
votes
5answers
264 views
0
votes
1answer
144 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 ...
0
votes
1answer
37 views

Explicit (General) formula for recursive definition.

I am given $a_n=3a_{n-1}+4^n$, $n=1,2,3,....$ and $a_0=1$. First four terms: $$ \begin{align} a_1&=3.1+4^1=3+4=7\\ a_2&=3.7 + 4^2 = 21 + 16 = 37 \\ a_3&=3.37 + 4^3 = 111 + 64 = 175\\ ...
6
votes
4answers
2k views

Geometric mean never exceeds arithmetic mean

This was a mathematical induction question proposed in a textbook, and I've exhausted multiple approaches (proving RHS - LHS > 0, splitting the fraction, fractional exponents, etc.) The geometric ...
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 ...
12
votes
5answers
276 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.
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
2answers
84 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 ...
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
1answer
83 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
1
vote
1answer
47 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. ...
0
votes
3answers
59 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
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 ...
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 ...
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
179 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. ...
1
vote
1answer
32 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
54 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, ...
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
0
votes
3answers
90 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 ...
21
votes
7answers
590 views

Illustrative examples of a phenomenon in the logic of mathematical induction

It is said (and I myself have said) that in some cases the easiest way to prove a statement by mathematical induction is to prove a stronger statement by mathematical induction, because then one has a ...
1
vote
1answer
29 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
39 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 ...
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 ...
1
vote
1answer
72 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
69 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 ...
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
239 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
77 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 ...
1
vote
2answers
82 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}} = ...
2
votes
1answer
38 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
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
1answer
69 views

Proving terms are rational using Mathematical Induction

I was able to do the first part of the question, in the second part (Proof by Induction), I showed it holds for $n=1$: Then I Assumed its true for $n=k$. ...
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 ...
2
votes
1answer
78 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 ...
0
votes
1answer
31 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
0answers
17 views

Induction for quantified statement with two discrete parameters

Given a quantified statement ∀n, n>0 (∃x, x>2k | x=2k+n) ( a subset of the natural numbers) This can logically this can be deduced as valid; however, I wish to use induction. Specifically I would ...
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$ ...