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

2
votes
3answers
60 views

Prove that the function $f(n) = n! - 2^n$ is positive for $n \ge 4$

n ∈ N and $P(n) : n! − 2^n > 0$. $P(4) : 4! − 16 > 0$ is true. $P(m)$ is true, m ≥ 4. $m! − 2^m > 0$, from step 3. $(m+1)! − 2^{m+1} = (m+1)\cdot m! − 2\cdot2^m$. $m+1 > 2$, from step 3. ...
2
votes
1answer
30 views

Prove $\sum_{r=0}^n 6r=3n(n+1)$ using induction

Prove$$\sum_{r=0}^n 6r=3n(n+1)$$using Induction I'm a little confused as to how I would calculate the latter
1
vote
1answer
108 views

Verification of a proof that the difference of two odd integers is not odd

Prove or disprove the difference of two odd integers is odd. Here was my answer: $m = 2s+1$ $n = 2t+1$ $m - n = (2s+1) - (2t+1)$ $= 2s - 2t$ $= 2(s-t)$ I then wrote the following: ...
-1
votes
1answer
60 views

Prove the formula for the sum of consecutive cubes [duplicate]

$$\sum_{k=1}^n k^3=\frac{n^2 (n+1)^2}{4}$$ Please help
0
votes
2answers
121 views

Derangement formula; proof by induction

Proof by induction that $ d_{n}=nd_{n-1}+(-1)^{n} $ where $d_{n}$ is number of $n$-element derangements.
0
votes
4answers
48 views

Induction Proof with a $\neq$ 1 [duplicate]

For $a \neq 1$ and $n>0$, $(1-a^{n+1})/(1-a)=1+a+a^2+...+a^n$ How do you prove this by induction?
0
votes
1answer
41 views

A basis for induction - What is the point of this argument?

I came across an argument in a book, and I'm wondering why we need this proof. Let $T \subset \mathbb{N}$ where: $0 \in T$ If $n-1 \in T$ then $n \in T$ Let $A = \mathbb{N}\backslash T$, we claim ...
0
votes
1answer
43 views

Inductively showing $g(s) = 3(g(s-1)+g(s-2))+1$ is odd for all $s$

How would I show this equation is odd by using the induction hypothesis: $$ g(s) = 3(g(s-1))+(g(s-2))+1 $$ I was thinking that I would prove $g(s)$ is odd by $g(s+1) = 3(g(s)+g(s-1))+1$. How would I ...
3
votes
4answers
106 views

Proof that $n^n<(n!)^2$ for $n>2$

Prove that $n^n<(n!)^2$ for $n>2$ I tried math induction, but couldn't prove that $(k+1)^{k+1}<((k+1)!)^2$.
0
votes
0answers
38 views

prove strong induction implies weak induction

So trying to prove: $[s(n_0)\wedge s(n_1)\wedge\cdots \wedge s(n_k)\wedge\forall_n[s(n-k)\wedge s(n-k+1)\wedge\cdots \wedge s(n-1)\wedge s(n)\rightarrow s(n+1)]\Rightarrow \forall_{n_0\le n}s(n)]$ ...
8
votes
0answers
340 views

Two (strictly related) proofs by induction of inequalities.

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
2
votes
2answers
33 views

If $a > b+1$ then there is $M > 1$ so that $a^n - b^n$ is divisible by $M$ for all positive integers $n$. Prove by induction that $M = a - b$.

The problem: It turns out that if $a$ and $b$ are positive integers with $a > b + 1$, then there is a positive integer $M > 1$ such that a $a^n − b^n$ is divisible by $M$ for all positive ...
1
vote
4answers
57 views

Prove using induction $2^{3n}-1$ is divisble by $7$ for all $n$ $\in \mathbb N$

Show that $2^{3n}-1$ is divisble by $7$ for all $n$ $\in \mathbb N$ I'm not really sure how to get started on this problem, but here is what I have done so far: Base case $n(1)$: ...
0
votes
1answer
33 views

How do I prove this by induction? [duplicate]

thank you for taking the time to help me with the question. I am struggling to use proof by induction for this formula: $$\sum_{k=0}^{n}k\times k! = (n + 1)! - 1$$ So far, I came up with: $$S(n) = ...
2
votes
3answers
37 views

Weak principle of induction for $5+10+15+\ldots+5n= \frac{5n(n+1)}{2}$

Show that $$5+10+15+\ldots+5n= \frac{5n(n+1)}{2}$$ Proving the base case $n(1)$: $5(1)= \frac{5(1)(1+1)}{2}$ $5 = \frac{5(2)}{2}$ $5 = 5$ Induction hypothesis: $n = k$ ...
0
votes
4answers
47 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
68 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
35 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
97 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
133 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
143 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
147 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
43 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
56 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
41 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} ...
1
vote
5answers
64 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
35 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
44 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
4k 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 + ...
-2
votes
1answer
54 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
63 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
55 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
49 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? ...
2
votes
2answers
88 views

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

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
43 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
297 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
53 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
25 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
62 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
53 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 ...
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 ...
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
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

Proof by induction when numbers are to powers

Prove by mathematical induction: $$ 2^n+3^n < 5^n$$
2
votes
7answers
322 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
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\\ ...
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 ...