Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

1
vote
1answer
17 views

Question around the following relation: $T(n,1) = n$, for a positive integer $n$, and for all $k\geq 1,\ T(n,k+1)=n^{T(n,k)}$.

I'm beginning the studies on number theory and then i'm facing the following problem that i couldn't solved yet: given a positive integer $n$ and being $T(n,1)=n$ and, for all $k\ge1$, ...
0
votes
1answer
41 views

How to prove that $(a+b-ab)^n+(1-a^n)(1-b^n) \geq n $ for $a,b\in [0,1]$ and $n\in\mathbb{N}$?

Let $a,b\in [0,1]$ and $n\in\mathbb{N}$. Prove the following inequality: $$(a+b-ab)^n+(1-a^n)(1-b^n) \geq n $$ I thought on using M Induction: Assuming that the inequality holds for $n=k,$ ...
0
votes
2answers
43 views

A simple mathematical induction proof.

Let n be a natural number, and let $ f:\{ i \in \mathbb{N} : 1 \le i \le n\} \rightarrow\mathbb{N} $ be a function. Show that there exists a natural number M such that $f(i) \le M $ for $1 \le i \le ...
0
votes
4answers
51 views

How to prove this equation by induction?

I am trying to prove this equation by mathematical induction $$f_{n+1}f_{n-1} = f_{n}^{2}+(-1)^n$$ is true where $f_{n} = $ the nth number in the Fibonacci sequence. I don't quite get how to do this ...
2
votes
2answers
34 views

Chaining Exponent Rules Together

I'm having trouble understanding why the following property is true and want to make sense of it before going ahead and using it in my proof by induction: $$2^{2^n}=2^{2^{n-1}}\times ...
0
votes
2answers
78 views

MIT OCW Assignment question Strong Induction

There are two types of creature on planet Char, Z-lings and B-lings. Furthermore, every creature belongs to a particular generation. The creatures in each generation reproduce according to certain ...
3
votes
1answer
56 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
51 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
67 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
82 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
43 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
410 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
39 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 ...
0
votes
2answers
39 views

Factorial inequality $2!\,4!\,6!\cdots (2n)!\geq\left((n+1)!\right)^n$ using induction

I want to show $2!\,4!\,6!\cdots (2n)!\geq\left((n+1)!\right)^n.$ Assume that it holds for some positive integer $k\geq 1$ and we will prove, $2!\,4!\,6!\cdots (2k+2)!\geq\left((k+2)!\right)^{k+1}$. ...
2
votes
0answers
50 views

Prove inequalities with induction

I have the following inequality to prove with induction: $$P(n): \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots\frac{1}{\sqrt{n}}>2-\frac{2}{n}, \forall n\in \mathbb{\:N}^*$$ I ...
1
vote
2answers
101 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
123 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*} ...
-2
votes
0answers
32 views

Transformers - Why more coils in second coil causes more voltage [closed]

I am learning about magnetic induction and transformers. I have coil1 which uses AC to create an oscillating magnetic field. I have ...
3
votes
2answers
34 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 ...
-8
votes
1answer
42 views

Mathematical induction to proof [closed]

Prove that $$\frac{1}{1}+\frac{1}{4}+\frac{1}{9}+...+\frac{1}{n^2} = \sum_{k=1}^n \frac{1}{n^2} \leq 2-\frac{1}{n}$$ Why would the answer said that 'the summation of (n+1) term from k 1/k^2 ...
-5
votes
1answer
36 views

Consider the expression n^5 + 9n. [closed]

a) Prove directly that $n^5 + 9n$ is even for all $n \in \Bbb N$ b) Prove by induction that $n^5 + 9n$ is divisible by $5$ for all $n \in \Bbb N$ c) Prove that for all $m \in \Bbb N$, $2 \mid m$ and ...
1
vote
1answer
52 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
30 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 ...
0
votes
2answers
193 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 ...
1
vote
1answer
68 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 $ ...
0
votes
0answers
28 views

Proving $L_{\mathbb{X}}i_{\mathbb{Y}}=i_{[\mathbb{X},\mathbb{Y}]}+i_{\mathbb{Y}}L_{\mathbb{X}}$ [duplicate]

Let $\mathbb{X}$, $\mathbb{Y}$ denote vector fields on $U \subset \mathbb{R}^n$. Prove the identity $L_{\mathbb{X}}i_{\mathbb{Y}}=i_{[\mathbb{X},\mathbb{Y}]}+i_{\mathbb{Y}}L_{\mathbb{X}}$ I ...
1
vote
0answers
49 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
44 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
73 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 ...
1
vote
3answers
38 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
48 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
79 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
42 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 ...
10
votes
7answers
924 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
199 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 )$$ ...
0
votes
1answer
21 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
32 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
96 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 ...
6
votes
0answers
192 views

Two (strictly related) proofs by induction of inequalities.

Predictably, I'm stuck with the inductive steps. Let $p_m$ be the largest prime factor of $a_n$ and set $\lim_{n\to \infty}\frac{\log a_n}{p_m}=1$. Suppose also this ratio converges to $1$ faster than ...
2
votes
1answer
83 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
33 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
59 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. ...
3
votes
2answers
42 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
29 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
46 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
4
votes
6answers
109 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
38 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
41 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
37 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
98 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$.