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 aimed ...

learn more… | top users | synonyms

0
votes
4answers
45 views

Use the principle of induction to show $2+6+18+\ldots+2\cdot 3^{n-1}=3^n-1$

Show that $$2+6+18+\ldots+2\cdot 3^{n-1}=3^n-1$$ Proving the base case when $n=1$: $2\cdot3^{1-1}=3^1-1\Leftrightarrow 2=2$ Now doing the induction: $2\cdot 3^{(n+1)-1}=3^{n+1}-1$ $2\cdot ...
2
votes
6answers
54 views

Prove that $n^2 > n+1 \quad\forall n \geq 2$ using mathematical induction

Prove $n^2 > n+1$ for $ n \geq 2$ using mathematical induction So I attempted to prove this, but I'm not sure if this is a valid proof. Base case, $n = 2$ $$ 2^2 > 2+ 1 $$ $n = k + 1$, ...
1
vote
1answer
30 views

Check this inequality using induction

I would like to prove this inequality using induction $$\sum_{k=1}^r \frac{2^k}{k^2} \le 9 \frac{2^r}{r^2}$$ The base case is simple enough: for $r=1$, we have: Here's my attempt at the inductive ...
1
vote
3answers
60 views

Confused about transfinite induction

QUESTION: I seem to be confused about how transfinite induction is carried out. I have looked at several examples and they seem to follow a procedure consisting of grounding the induction, proving the ...
4
votes
6answers
113 views

the purpose of induction

After getting an answer (in a comment) from peter for this question I have a follow up question. If, in all horses are the same color problem for example, we need to use reason, reason which is ...
1
vote
3answers
44 views

number of edges induction proof

Proof by induction that the complete graph $K_{n}$ has $n(n-1)/2$ edges. I know how to do the induction step I'm just a little confused on what the left side of my equation should be. $E = n(n-1)/2$ ...
3
votes
4answers
100 views

how to point out errors in proof by induction

I have searched for an answer to my question but no one seems to be talking about this particular matter.. I will use the all horses are the same color paradox as an example. Everyone points out ...
0
votes
2answers
39 views

Proof by induction, is my proof incorrect?

Claim: $-1+2+5+8+...+(3n-4) = \frac{n}{2}(3-5n)$ Base: $3(1)-4=-1$ $\frac{1}{2}(3-5(1))=-1\,\,$ Induction: $-1+2+5+8+...+(3k-4)+(3(k+1)-4) = \frac{k+1}{2}(3-5(k+1))$ ...
0
votes
1answer
30 views

Error in induction proof

What is wrong with the following proof? Is it the fact that 5, 6 , 7 was never verified (base cases) because we never set a bound for k? Claim: Any integral amount of postage greater than or equal ...
0
votes
1answer
37 views

Proof by induction that if $a_0 = 1$ and $a_n = n + 2 a_{n-1}$, then $a_n \ge 2^n + n^2$.

I have that $a_0 = 1$ and $a_n = n + 2 a_{n-1}$ for $n \geq 1$. Now I need to proof by induction that $a_n \geq 2^n + n^2$. I already have my base case. My hypothesis would be $a_{n-1} \geq 2^{n-1} ...
0
votes
3answers
33 views

Concise induction step for proving $\sum_{i=1}^n i^3 = \left( \sum_{i=1}^ni\right)^2$

I recently got a book on number theory and am working through some of the basic proofs. I was able to prove that $$\sum_{i=1}^n i^3 = \left( \sum_{i=1}^ni\right)^2$$ with the help of the identity ...
1
vote
1answer
34 views

Show that $\prod_{i=2}^n \left(1-\frac{1}{i^2}\right) = \frac{n+1}{2n}$for $n \in \Bbb{N}$, $ n \ge 2$

Use mathematical induction to shoe that fpr any $n\in N$, if $n\ge2$, then $$\prod_{i=2}^{n}\left(1-\frac{1}{i^2}\right)=\frac{n+1}{2n}$$ So I understand what's happening up until the first red ...
0
votes
2answers
43 views

Using mathematical induction on natural numbers to show ∀n. 0+2+4+…+2·n = n·(n+1)

I'm working through a practice problem and have the solution but don't understand how the rearranging happens: I have: \begin{align*} \ldots &= \big(n(n+1)\big) + 2(n+1) \\ &= (n + 2)(n + ...
13
votes
11answers
3k views

Prove that $1 + 4 + 7 + · · · + 3n − 2 = \frac {n(3n − 1)}{2}$

Prove that $$1 + 4 + 7 + · · · + 3n − 2 = \frac{n(3n − 1)} 2$$ for all positive integers $n$. Proof: $$1+4+7+\ldots +3(k+1)-2= \frac{(k + 1)[3(k+1)+1]}2$$ $$\frac{(k + 1)[3(k+1)+1]}2 + ...
0
votes
1answer
49 views

Proof by induction of this formula? [duplicate]

$2^0+2^1+2^2+...+2^n$ for $n ∈ \mathbb{N}$ U ${0}$. I made a conjecture that this is $2^{n+1} - 1$. Now I have to prove it by induction. I tested the base case where it's equal to zero, and it ...
4
votes
3answers
58 views

Show: $\left(\sum_{k=0}^n a_k\right)^2\leqslant (n+1)\sum_{k=0}^n a_k^2$

Show: $\left(\sum_{k=0}^n a_k\right)^2\leqslant (n+1)\sum_{k=0}^n a_k^2$ for $n\geqslant 0$ and $a_k\in\mathbb{Z}_{\geq 0}$. Wanted to show this by induction: $n=0: a_0^2\leqslant a_0^2$ Assume it ...
2
votes
2answers
50 views

Proof by induction, or without it if possible?

I was given a task to prove: $$ \frac{1}{(x+1)(x+2)\ldots(x+n)}=\frac{1}{(n-1)!}\sum_{i=1}^n\binom{n-1}{i-1}\frac{(-1)^{i-1}}{x+i} $$ I am almost 100% sure this is best solved by induction but to be ...
-3
votes
2answers
46 views

Use mathematical induction to prove $\sum_{i=1}^{n}(2i+4)=n^2+5n$

Prove: $$ \sum_{i=1}^{n}(2i+4)=n^2+5n \textrm{ for each positive integer } n $$ So I'm not exactly sure how to do this problem for my math class. Can any mathematicians out there help me? ...
1
vote
2answers
59 views

Prove $1 + \frac{1}{4} + \frac{1}{9} + \cdots + \frac{1}{n^2} < 2 - \frac{1}{n}$ by Induction

The Question Prove $1 + \frac{1}{4} + \frac{1}{9} + \cdots + \frac{1}{n^2} < 2 - \frac{1}{n}$ where $n\ge2$ and $n$ is an integer by Induction My Work Basis Step: 1 + $\frac{1}{4} = ...
1
vote
3answers
42 views

Show that $n!<n^n $ where $n>1$ and is a Positive Integer

Basis Case: $2! = 2\times1 = 2$ $2^2 = 4>2$ Inductive Hypothesis: $k!<k^k$ Induction Step: $k!<k^k$ $k!(k+1) < k^k(k+1)$ $(k+1)! < k^{k+1} + k^k$ I'm confused on where to go ...
3
votes
5answers
248 views

Proving formula for sum of squares with binomial coefficient

$$\sum_{k=0}^{n-1}(k^2)= \binom{n}{3} + \binom{n+1}{3}$$ How should I prove that it is the correct formula for sum of squares? Should I use induction to prove the basis? Any help is appreciated.
2
votes
2answers
51 views

How to get $\sqrt {k} + \frac{1}{\sqrt{k+1}}$ in the form $\frac{\sqrt{k^2} + 1}{\sqrt{k+1}}$?

I was wondering if it is possible to get $\sqrt {k} + \dfrac{1}{\sqrt{k+1}}$ in the form $\dfrac{\sqrt{k^2} + 1}{\sqrt{k+1}}$, and if so, how? I ask this, because I'm following this answer, and I get ...
1
vote
1answer
22 views

How to prove by this type of question by Induction (If $a_1 = 6$ and $a_{m+1} = 2a_m - 3m + 2$ for $m \geq 1$, then $a_n = 2^n + 3n + 1$)

Please do not tell me how to prove this exact question. I would like to know how to go about proving the following type of question by induction: If $a_1 = 6$ and $a_{m+1} = 2a_m - 3m + 2$ for $m ...
1
vote
4answers
49 views

Extending $2^n > n $ from set of natural to set of real numbers

I was given a task to prove that $2^n>n$ for any $n \in N \cup \{0\}$. I am aware that this can be solved by induction and that the solution is pretty easy but instead of meddling with induction ...
1
vote
1answer
59 views

Counting regions in a disk that has been cut by lines

Let $n$ be a positive integer, and $n$ lines drawn in a ring such that each one of them intersects with all of them, but no more than two intersect at one point. prove that the lines cut the disk ...
1
vote
2answers
29 views

Explicit formula for recurrence relation

I am given recurrence relation : an = 5an/2 + 3n, for n = 2,4,8,16... and a2 = 1. I found first 4 terms and I don't see a pattern. a4 = 5*1 + 3*4 = 17 a8 = 5*17 + 3*8 = 109 a16 = 5*109 + 3*16 = 593 ...
-2
votes
1answer
68 views

Finding number of regions on the circle that is cutting by chords using mathematical induction [closed]

Let $n$ be a positive integer, and suppose that $n$ chords are drawn in a circle such a way that each chord intersects every other, but no three intersects at one point. Use mathematical induction to ...
0
votes
1answer
24 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 ...
0
votes
2answers
27 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
81 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
26 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
0answers
49 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
258 views

Proof by induction when numbers are to powers

Prove by mathematical induction: $$ 2^n+3^n < 5^n$$
2
votes
7answers
315 views

Proof by induction that $2^n - 1 > n^2$

i want to prove that $\forall n\geq 5$ $$2^{n}-1 > n^{2}$$ so the basis is trivial, and in the induction step (n+1), i stuck. i get : $(n+1)^{2} = n^{2} + 2n + 1 < (2^{n} -1)+ 2n+1 = 2^{n} ...
0
votes
1answer
27 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\\ ...
0
votes
3answers
70 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
110 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
41 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$ ...
0
votes
2answers
75 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
34 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
128 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
45 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
67 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 >= K. The cards all have different number. ...
0
votes
1answer
56 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 ...
12
votes
5answers
264 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
43 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 ...
3
votes
2answers
33 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
88 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
48 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
40 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. ...