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

3
votes
1answer
82 views

Writing a proof of the convergence of a series defined recursively

Define the sequence $a_n$ recursively by $a_1=1$ and $$a_{n+1}=\frac13\left(a_n^2+\frac1n\right)$$ (a) Prove, by induction or otherwise, that $(a_n)$ is decreasing. (b) Prove that the series ...
1
vote
1answer
91 views

Induction and basic assumptions in Graph Theory

I am beginning to work through a text in graph theory and have a couple of questions. 1) Can we always assume a graph is nonempty, i.e., if a graph $G$ has order $n$, do we assume $n\in \{1,2,...\}$? ...
1
vote
3answers
82 views

Want to ensure my proof is rigourous enough.

Question. Prove: $ 0 \leq x < y $ then $ x^n < y^n$ $ \forall n \in \mathbb{N} $ I'm particularly bad at proving obvious things but here it goes. ( please be super strict on analyzing my proof ...
3
votes
2answers
84 views

Is saying that $2^n+1<2^n\cdot2$ for $n \in \mathbb N$ is true enough to end the proof?

For $n \in\mathbb N$ I have to prove, using mathematical induction: $$\forall n\in\mathbb N(n<2^n)$$ It holds for $n=1$ So I assume $\forall n\in\mathbb N(n<2^n)$ alright. I need to prove ...
3
votes
1answer
52 views

Existence of two unrelated pairs in a constrained relation

Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that: $$ \exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ ...
4
votes
6answers
440 views

Question on induction technique

When one uses induction (say on $n$) to prove something, does it mean the proof holds for all finite values of $n$ or does it always hold when even $n$ takes $\pm\infty$?
1
vote
2answers
48 views

Prove the inequality $(n+1)^4 < 4n^4$ for $n\geq 3$ by induction

The inequality I'm concerned with is $(n+1)^4 < 4n^4,\ n\geq 3$. I'm not sure how induction is supposed to work here. If I assume $(k+1)^4<4k^4$, I cannot see how this helps show ...
1
vote
2answers
127 views

An exercise from Knuth's book - Proving a formula by induction

I would like to find a formula for this sum: $$ \frac{1^3}{1^4+4} - \frac{3^3}{3^4+4} + \frac{5^3}{5^4+4} - ... + \frac{(-1)^n(2n+1)^3}{(2n+1)^4+4} $$ The answer given (Knuth's book, The Art of ...
3
votes
3answers
128 views

Prove the following relation:

I must prove the relation $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$ I got this far before I got stuck: $\begin{eqnarray*} ...
3
votes
2answers
67 views

Proving that a function is absolutely monotonic on a given interval

According to the following Wolfram Alpha article: http://mathworld.wolfram.com/AbsolutelyMonotonicFunction.html, the function $f(x) = -\ln(-x)$ is absolutely monotonic on the interval $[-1,0)$. My ...
1
vote
1answer
115 views

Use induction to prove that Legendre polynomials solve the corresponding differential equation

I was given a "classical" homework question where I have to prove that the Legendre polynomials solve the differential equation: $\frac{d}{dx}[(1-x^2)\frac{d}{dx}P_n(x)] + n(n+1)P_n(x) = 0$ However, ...
0
votes
2answers
33 views

Induction proof for $x \le y $

So these are $x \in \{1 ... i\}$ and $y \in \{ i + 1 ... n\}$, for $i, n \in \mathbb N$. I want to prove it for every $x \le y $. I know it`s easy but the solution is escaping me. I have tried with ...
-1
votes
2answers
197 views

Proof by induction that $B\cup (\bigcap_{i=1}^n A_i)=\bigcap_{i=1}^n (B\cup A_i)$

$\displaystyle B\cup (\bigcap_{i=1}^n A_i)=\bigcap_{i=1}^n (B\cup A_i)$ I was able to prove this without using induction, however I am supposed to prove it using induction. How should I go about ...
2
votes
1answer
97 views

Number of ways to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles

How many ways are there to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles? Rotating is allowed. Progress Let $T_n$ be the number of ways; then $T_n = T_{ n-1} + T_{ n-2} + 1 $ ...
1
vote
0answers
54 views

can anyone prove this with induction?

Suppose that we have a sequence of numbers $x_1,x_2,\ldots,x_n$ called $S$. A subsequence of $S$ is a sequence obtained by omitting some elements of $S$. An increasing subsequence of $S$ called $IS$ ...
3
votes
1answer
107 views

Model of Robinson Arithmetic but not Peano Arithmetic

I am curious how can structure of with linear successor function that do not admin induction looks like. In other words I would like to see structure of Peano Arithmetic without induction. I believe ...
1
vote
3answers
80 views

Prove that $1+2^1+2^2+\ldots +2^n=2^{n+1}-1$ using induction

For all integers $n\ge 1$ prove the following statement using mathematical induction. $$1+2^1+2^2+\ldots +2^n=2^{n+1}-1$$ The first part of the question ask me to prove the base step: So I set ...
2
votes
3answers
49 views

Compare inequalities in a proof by induction

I am solving a proof by induction example. But I ended up with my hypothesis $$ a_{n-1} \geq \frac{2^n}{2}+n^2-2n+1 $$ and my inductive step $$ a_{n-1} \geq \frac{2^n}{2}+\frac{n^2}{2}-\frac{n}{2}. ...
0
votes
4answers
54 views

How to prove the sequence given by $a_{n+1}=s+a_n^2$ is monotonic increasing?

Let $s$ be $0\:\le \:s\le \:\frac{1}{4}$ and consider this sequence: $a_1\:=\:s$ $a_{n+1}\:=\:s\:+\:a_n^2$ I want to prove that is monotonic sequence, so I thought about induction or assume in ...
1
vote
4answers
112 views

Prove or disprove $n^2+41n+41$ is a prime number for every integer $n$

Prove or disprove $n^2+41n+41$ is a prime number for every integer $n$ I started with the base step: $n(0) = 0^2+41(0)+41 = 41$ But I have no idea how to proceed in proving this. Any tips or ...
0
votes
2answers
63 views

Mathematical induction help, please.

Use the second principle of mathematical induction to show that if f(1) is specified and a rule for finding f(n+1) from the values of f at the first n positive integers is given. Then f(n) is uniquely ...
11
votes
7answers
1k views

Prove by induction that an expression is divisible by 11

Prove, by induction that $2^{3n-1}+5\cdot3^n$ is divisible by $11$ for any even number $n\in\Bbb N$. I am rather confused by this question. This is my attempt so far: For $n = 2$ $2^5 ...
2
votes
2answers
208 views

Proof that this diagram commutes

This is an exercise in a book I'm reading: Define an $\mathbb R$-linear isomorphism $f_n : \mathbb C^n \to \mathbb R^{2n}$ by $$(x_1 + iy_1, x_2 + iy_2, \dots) \mapsto (x_1, y_1, x_2, y_2, \dots )$$ ...
1
vote
1answer
42 views

Can you use proof by contradiction inside simple induction?

During a proof using simple induction, I assumed P(k) is true. Now in order to show P(k+1) is true using P(k), can I do a proof by contradiction on P(k+1) and say P(k) would be wrong if P(k+1) is ...
-1
votes
1answer
44 views

Can I prove these series with limit a using induction?

This is the equation: It is true for: E a normed space and $(a_n)_{n \in \mathbb N}$ a convergent sequence with limes a. $$s_k = \frac1k\sum^k_{n=1} a_n \rightarrow a$$ $a = \lim_{n\rightarrow ...
3
votes
4answers
151 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 ...
1
vote
1answer
115 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
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 ...
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
2answers
48 views

Prove that $\sum_{r=1}^nr(r+1)=\frac{n(n+1)(n+2)}{3}$ using induction

$$\sum_{r=1}^nr(r+1)=\frac{n(n+1)(n+2)}{3}$$ could you help me with how exactly I work this out?
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
votes
1answer
63 views
4
votes
6answers
134 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 ...
0
votes
2answers
124 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 ...
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
40 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)]$ ...
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$ ...
1
vote
4answers
58 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)$: ...
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 ...
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) = ...
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
3answers
161 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$ ...
2
votes
2answers
68 views

Why is the invariant of the following state machine (2 mod 5) OR (3 mod 5)?

Consider a state machine with tuple of numbers describing its state, i.e. $(i,j)$ such that $i \geq 0$ and $j \geq 0$. The initial state is $q_0 =(i,j) = (15, 12)$ There are only two transitions ...
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
61 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 ...
1
vote
1answer
63 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 ...
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 + ...