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

2
votes
3answers
48 views

Proving by induction: $ \frac{1\cdot3\cdot5\cdot \ldots \cdot (2n-1)}{1\cdot2\cdot3\cdot\ldots\cdot n} \leq 2^n $

WTS $ \frac{1\cdot3\cdot5\cdot \ldots \cdot (2n-1)}{1\cdot2\cdot3\cdot\ldots\cdot n} \leq 2^n $ for all natural $n$. Have checked $P_1$, and assumed $P_k$. Trying the following argument: $P_{k+1} ...
0
votes
3answers
45 views

Proving by induction that $(n^2)!>(n!)^2$ for $n \geq 2$

I'm trying to prove that $(n^2)!>(n!)^2$ for $n \in [2,\infty) \cap\mathbb{Z^+}.$ Ok, here's what I've tried: $n \geq 2,$ $(n^2)!>(n!)^2$ ...
0
votes
4answers
59 views

Proving (by induction) the inequality $ \sum_{i=1}^n \frac1{\sqrt i} > 2(\sqrt{n+1}-1), \forall n \in \mathbb N$

Trying to prove that $$ \sum_{i=1}^n \frac1{\sqrt i} > 2(\sqrt{n+1}-1), \forall n \in \mathbb N$$ using induction. My only attempt so far has consisted of squaring both sides (during the ...
1
vote
1answer
22 views

Proof by induction, simplification step

i have to prove (3/4)(5^(k+2) -1) I have so far (after using inductive hypothesis etc): (3/4)(5^(K+1) -1) +3*5^(K+1) I can't seen to find a useful common factor to simplify although i'm sure it ...
1
vote
2answers
43 views

Proof by induction - inequality question

I am trying to understand how to do proof by induction for inequalities. The step that I don't fully understand is making an assumption that n=k+1. For equations it is simple. For example: Prove that ...
3
votes
1answer
36 views

$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}}$

I'm supopsed to show that if $m$ and $n$ are non-negative integers then $$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}} = \left\{ \begin{array}{l l} 1 & \quad \text{if $n=0$}\\ ...
0
votes
1answer
30 views

Recursive sequence problem

$$U(n+1) = (6+U(n))^{1/3},\text{ and } U(0) = 1.$$ Prove by induction that for all positive integers $n, U(n)$ is increasing. Prove by induction that for all positive integers $n, U(n) \leq 2$ ...
2
votes
2answers
62 views

Consider the sequence defined recursively by $U(n+1) =\frac{1}{3-U(n)}$ and $U(0) = 2$. [closed]

Prove by induction that for all positive integers $n, U(n)$ is decreasing Prove by induction that for all positive integers $n, U(n) > 0$ (namely, the sequence is bounded from below) Does the ...
1
vote
4answers
86 views

Determine which Fibonacci numbers are even

(a) Determine which Fibonacci numbers are even. Use a form of mathematical induction to prove your conjecture. (b) Determine which Fibonacci numbers are divisible by 3. Use a form of mathematical ...
3
votes
3answers
52 views

Is it possible to use mathematical induction to prove a statement concerning all real numbers, not necessarily just the integers? [duplicate]

I am referring to the part of proof by mathematical induction where you show that "if it is true for one value k then it is true for the value k+1". Does proof by induction work over all real numbers? ...
1
vote
3answers
28 views

Question regarding Strong Principle of Induction

I'm currently studying Discrete mathematics from a book by Normal L. Biggs and i don't understand the thinking about an example on Strong Principle of Induction, The example i need help ...
2
votes
2answers
36 views

Prove by induction that $\sum_{i=1}^n i!\times i=(n+1)!-1$ for all $n\in \mathbb{N}$

So far I have, If $P(n):\sum_{i=1}^n i!\times i=(n+1)!-1$, then $P(1):\sum_{i=1}^1 i!\times i=1$ and $(1+1)!-1=1$ , so P(1) is true. I know I now have to assume P(K) is true, such that ...
2
votes
3answers
44 views

Strong Induction, assuming k<n where k and n are not numbers

In strong Induction for the induction hypothesis you assume for all K, p(k) for k If for example I am working with trees and not natural numbers can I still use this style of proof? For example if I ...
2
votes
2answers
21 views

Deduce that the next integer greater

Deduce that the next integer greater than $(3+\sqrt 5)^n$ is divisible by $2^n$ I tried expanding it by binomial theorem but got nothing
28
votes
13answers
3k views

Why doesn't mathematical induction work backwards or with increments other than 1?

From my understanding of my topic, if a statement is true for $n = 1,$ and you assume a statement is true for arbitrary integer $k$ and show that the statement is also true for $k + 1,$ then you prove ...
0
votes
1answer
32 views

Complex Polynomial That is n Times Differentiable: A Concern

I'm looking at a question that asks me to show that: If a function $f$ is known to be $n$-times differentiable in a domain $D$ and if $\forall{z\in{D}}\ \ f^{(n)}(z)=0$, then $f$ is a polynomial ...
-1
votes
3answers
58 views

How to prove that for any $n$ in $\mathbb{N}$ that $(\frac{3}{2})^n \ge n$?

Well, I was trying to do that using proof by induction and my attempt is : Base case : $(\frac{3}{2})^0 \ge 0$, true Assumption : $(\frac{3}{2})^k \ge k$. I've multiplied both sides by $(\frac{3}{2})$ ...
0
votes
1answer
27 views

Confused by step in an inductive proof of arithmetical progression

In the book "What is Mathematics?" there is a section that provides an inductive proof of the arithmetic progression. Part of this proof is: $\frac{r(r+1)+2(r+1)}{2}=\frac{(r+1)(r+2)}{2}$ I don't ...
1
vote
1answer
39 views

Proof for positive integer

Prove that for any positive integers $m$ and $n$, there exists a set of $n$ consecutive positive integers each of which is divisible by a number of the form $d^m$ where $d$ is some integer in ...
0
votes
4answers
55 views

Find a formula for $1 + 3 + 5 + … +(2n - 1)$, for $n \ge 1$, and prove that your formula is correct.

I think the formula is $n^2$. Define $p(n): 1 + 3 + 5 + \ldots +(2n − 1) = n^2$ Then $p(n + 1): 1 + 3 + 5 + \ldots +(2n − 1) + 2n = (n + 1)^2$ So $p(n + 1): n^2 + 2n = (n + 1)^2$ The equality ...
2
votes
3answers
66 views

Induction: Prove that it is possible to seat people in a circle so that everyone sits beside a friend

Use induction to prove the following: If each person in a group of $n$ people is a friend of at least half the people in the group, then prove that it is possible to seat them in a circle so that ...
0
votes
2answers
63 views

I can prove that the series is greater than $\frac{1}{2}$ however i can't prove that it is greater than $\frac{13}{24}$ [duplicate]

Prove that for any positive integer $n>1$ $$ \frac{1}{n+1} + \frac{1}{n+2} + \frac{1}{n+3} \ldots + \frac{1}{2n} > \frac{13}{24} $$ I can prove that the series is greater than $\frac{12}{24}$ ...
2
votes
1answer
33 views

odd/even binomial coefficient identity [duplicate]

For all n\geq1 : $$\left(\begin{matrix}2n\\ 0 \end{matrix}\right) +\left(\begin{matrix}2n\\ 2 \end{matrix}\right) +\left(\begin{matrix}2n\\ 4 \end{matrix}\right) + \ldots ...
0
votes
1answer
21 views

Proof regarding effect of row operations on determinants>

Let $A,B \in K^{n,n}$ and suppose $B$ is obtained from $A$ by adding $\lambda$ times row $j$ to row $i$. Prove $det(A)=det(B)$. My Attempt I tried to use proof by induction for this . Take ...
1
vote
1answer
64 views

Prove $x_n \leq x_{n+1}$ for all $n$ by induction

Prove $x_n \leq x_{n+1}$ for all $n$ by induction. I am reading this example from "Understanding Analysis" by Abbott (page 10). He says the multiple across the inequality by $1/2$ and then add 1 to ...
1
vote
1answer
47 views

I need some quick factoring tips and tricks

Prove that for all $n \in \mathbb N$, $0^2 + 1^2 + 2^2 + \ldots + n^2 = \frac {n(n + 1)(2n + 1)}{6}$. Define $ p(n)=0^2 + 1^2 + 2^2 + \ldots + n^2$. Then: \begin{align*}p(n + 1)&=0^2 + 1^2 + 2^2 ...
0
votes
2answers
34 views

Induction question - sums

I just proved $\sum_{i=1}^n i^3 = [\frac{n(n+1)}{2}]^2$ using mathematical induction. I have to prove it for $i^4$ now. So would that be $\sum_{i=1}^n i^4 = [\frac{n(n+1)}{2}]^3$ ?
0
votes
2answers
33 views

Deducing formula for nth term in sequence and validate using principles of induction

I a working my way through some old exam papers but have come up with a problem. One question on sequences and induction goes: A sequence of integers $x_1, x_2,\cdots, x_k,\cdots$ is defind ...
0
votes
0answers
23 views

Proving two ordered $k$-tuples are equal iff each of their coordinates are equal - though induction

Prove that two ordered $k$-tuples are equal iff each of their coordinates are equal. (Use the inductive definition) For any integer $n \geq 2, (a_1, a_2, \ldots, a_n) = (b_1, b_2, \ldots , b_n)$ if ...
1
vote
2answers
61 views

Intricate proof by induction

Help the King out... $$2+8+24+64+...+(n)(2^n)=2(1+(n-1)(2^n))$$ I am at the step where I am proving $P(k+1)$ to be true: $$2(1+(k-1)(2^k))+(k+1)((2)^{k+1}))=2(1+((k+1)-1)(2^{k+1}))$$
1
vote
3answers
98 views

Prove by induction that (5^(n))-1 is divisible by 4 for all natural numbers n.

Prove by induction that $5^n-1$ is divisible by $4$ for all natural numbers $n$. I got $P(k+1)=5^{k+1}-1$ but I don't where to go now.
0
votes
2answers
47 views

Proof by induction of a sum.

I am at the step where I am proving $P(k+1)$: $$2^k-1+2^k=2^{k+1}-1$$ How am I going to make these equal? Ps: Just realized this is just an exponent rule, I need coffee.
0
votes
1answer
83 views

How can I prove the correctness of this multiplication algorithm?

I want to know how I can prove that this algorithm is correct: ...
0
votes
1answer
64 views

Prove this binomial sum by induction

Can someone help me with this one? Prove by mathematical induction For $$n\geq1$$ $$\displaystyle{\sum^n_ {k=0} k^n\binom{n}{k}(-1)^k= (-1)^nn!}$$ It's easy to see that for $$n=1$$ ...
0
votes
0answers
58 views

Matrix Induction proofs using $\rm mod$.

Please could someone advise me on where to even start with this question. Thanks in advance Let $A$ be an $n\times n$ matrix, for some $n\geqslant 1$. Given any prime number $p\gt1$, write $A_p$ for ...
2
votes
0answers
136 views

Homework Question for a 15 year old

My younger brother(age: 14 years 7 months) and his classmates were given a set of eight questions by his class-teacher, which included the following two questions: (i) Find, if you can, the fallacy ...
3
votes
1answer
122 views

Why is this more-detailed proof more acceptable than its trivial counterpart?

Say that we're asked to give a proof of 'proof by induction'. i.e. for some property $P$, proving that $$\forall n,P(1) \wedge [P(k) \implies P(k+1)] \implies \forall n, P(n)$$. Now, I understand ...
0
votes
1answer
95 views

Is this a Correct Proof of the Principle of Complete Induction for Natural Numbers in ZF?

I have reviewed a number of previous posts on this subject without finding an answer to my own point of interest, which is a proof that is closely related to ZF axioms and doesn't pre-suppose results ...
3
votes
1answer
36 views

Number of ways to color such that one color always leads

There are n boxes drawn out in a line. We have two colors, blue and red. We start coloring boxes from left to right. At any instant we want to color the boxes in such a way that number of boxes ...
0
votes
1answer
63 views

Show that $b_n > b_{n-1}$ where $\frac{a_n}{b_n}$ are the n:th harmonic number

Let $H_n=\frac{a_n}{b_n}$ where $H_n$ is a n:th harmonic number and $a_n$ and $b_n$ are coprimes. 1/ If $n$ is a prime power, show that $b_n > b_{n-1}$ 2/ Find the integer factorization of ...
0
votes
2answers
79 views

Integral of $\sin^n(x)$, recurrence relation, some properties

Practicing the manipulation of recurrence relations, I'm stuck on this : Defining $I(n)=\int_{0}^{\pi/2}sin^n(x)dx$, I got the recurrence relation $nI(n)=(n-1)I(n-2)$ for $n\ge2$. Now I'm also ...
0
votes
1answer
21 views

Lemma about a prime ideal in a commutative ring with identity

I am trying to prove the Cyclotomic polynomial is irreducible over $\mathbb{Q}[x]$ for any prime $p$ using Eisenstein's Criterion. However, I would like to be more specific and prove the following ...
3
votes
5answers
105 views

$6^{(n+2)} + 7^{(2n+1)}$ is divisible by $43$ for $n \ge 1$

Use mathematical induction to prove that 6(n+2) + 7(2n+1) is divisible by 43 for n >= 1. So start with n = 1: 6(1+2) + 7(2(1)+1) = 63 + 73 = 559 -> 559/43 = 13. So n=1 is divisible Let P(k): ...
0
votes
9answers
103 views

Proof by induction: Prove that $6$ divides $9^n - 3^n$

Induction: prove that $6| 9^n - 3^n$, where $n$ is a positive integer inductive step: trying to prove $6| 9^{k+1} - 3^{k+1}$, $= 9^k \cdot 9 - 3^k \cdot 3$ $= 6(\frac3 2 \cdot 9^k - \frac1 2 \cdot ...
1
vote
2answers
32 views

Induction: the complement A1 U A2 … U An is the intersection of Ac 1, Ac 2, …, Ac n

Prove by induction that the complement of $ A1 \cup A2...An = A1^c \cap A2^c ...\cap An^c$ My approach: basic step is true, $\overline A1 = A1^c$, then assume $ A1 \cup A2...Ak = A1^c \cap A2^c ...
0
votes
3answers
62 views

Induction: prove $2n^2 < 10\cdot n!$

Prove that $2n^2 < 10\cdot n!$, where $n$ is a positive integer My approach: $P(1)$ is true, and I'm trying to prove that $2(k+1)^2 < 10 (k+1)!$ Assume $2k^2 < 10\cdot k!$, and $2k^2 * ...
1
vote
2answers
34 views

Proof by induction using logarithms

I have come across a question while studing for my exams prove $$\log_2 x < x \text{ when }x>0$$ I know I have to solve it using a base case eg when $x=1$ then assume a inductive step $x=k$ is ...
1
vote
1answer
32 views

Inductive step assumption for all numbers up to $n$

I know that the inductive step should be "for all $n$ (if $P(n)$ then $P(n+1)$)" and NOT "if (for all $n$ $(P(n)$)) then (for all $n$ ($P(n+1)$))" - see this answer. But can it be like "if (for all ...
0
votes
3answers
72 views

Prove that $n = 2a + 3b$.

How can I prove by induction that for any natural number $n$ there exists integers $a,b$ so that $2a+3b=n$ I can prove the base case, and I can imagine why it works but how can I prove it ...
0
votes
2answers
32 views

Using induction to prove an equation

Use induction to show that $n(n + 1) < 2^n$ for all $n \ge 5$. Assuming is true for $n = 5$, $5(6) < 2^5$ is true. How can I prove this using induction?