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
2answers
36 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
36 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
49 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 ...
4
votes
6answers
395 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
89 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 ...
-2
votes
0answers
32 views

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

I am learning about magnetic induction and transformers. I have coil1 which uses AC to create an oscillating magnetic field. I have ...
3
votes
0answers
33 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 \\ ...
3
votes
2answers
31 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 [on hold]

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
34 views

Consider the expression n^5 + 9n. [on hold]

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 ...
0
votes
2answers
29 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
vote
1answer
66 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
26 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
43 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 ...
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 ...
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 ...
0
votes
2answers
34 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 ...
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}. ...
10
votes
7answers
922 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 ...
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
31 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 ...
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, ...
1
vote
0answers
33 views

Proof by induction for F_t [closed]

If one has $F_t$, $F_1$, $F_2$..... how can one get $F_{t+1}$. I was thinking of just adding them, but then what if you dont have F_t, how can you get F_t+1 from F_1 and F_2
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
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. ...
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
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
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
-1
votes
3answers
54 views

prove that if n is odd then 5n +3 is even [closed]

I have been trying to find online tutorials but have been struggling. some help plus working out will be fully appreciated
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
97 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
21 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)]$ ...
6
votes
0answers
190 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
2answers
15 views

Induction Proof Question: finding a divisor then proving it

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
46 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
28 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
30 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
44 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
50 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
28 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
3answers
44 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
107 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
41 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
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 ...
0
votes
2answers
38 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
28 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 ...