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
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
20 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
54 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
65 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
61 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
29 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
96 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
81 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
93 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
101 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?
1
vote
1answer
28 views

Induction proof $2^{n+1}-1$ when n is 50

There are 50 of YES or NO questions. Supposed store them into a binary tree. Each path from root to leaf implies a possible answer to the questions. The number of vertices for $n$ question is ...
0
votes
0answers
18 views

I need to prove by induction $(n-1)!\int_0^1{dx_1\:\ldots\:\int_0^1{dx_n\:\delta(x_1+\ldots+x_n-1)}}=1$ [duplicate]

Prove by induction $$(n-1)!\int_0^1{dx_1\:\ldots\:\int_0^1{dx_n\:\delta(x_1+\ldots+x_n-1)}}=1$$ I can check the cases $n=1,2,3$ but I don't know how the prove the general case. Thank you very much! ...
1
vote
1answer
29 views

Summation Induction when lower limit is not 1

The question is use induction to prove that $$\sum_{r=2}^n (r^2+r+1)r! = (n+1)^2n!-4$$ I don't understand how to even get the P1 statement since when I substitute r = 2 into the LHS and n = 1 into ...
0
votes
2answers
94 views

Prove the commutativity property of addition of natural numbers by induction

the background I'm allowed to deal with to solve this problem is as follows: Definition of +: \begin{equation} m+0=m\quad \text{for all}\quad m \in \mathbb{N} \\ m+(k+1) = (m+k)+1 \end{equation} in ...
1
vote
3answers
62 views

Help: Proof via Induction homework problem.

(b) Prove that for every integer $n \ge 1$, $$1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$$ This is the second part of a two part question. Part (a) was the following: ...
1
vote
2answers
52 views

Mix of contour integrals and mathematical induction?

I'm trying to compute $I:= \int_ {0}^{2\pi} \cos ^{2n} \theta d \theta $ Based on the following theorem: $ \Large\int_{0}^{2\pi} F(\cos\theta,\sin\theta)d\theta = \int_{\left|z\right| = 1} ...
0
votes
2answers
56 views

Prove that for every integer $n \ge 1$, $1 + \frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+ … +\frac{1}{\sqrt{n}}\le 2\sqrt{n}$

I understand that this is an induction question. I start with the base case (n=1): $$1 < 2 \tag{That works!}$$ Induction step: Assume the statement works for all $n = k$, Prove for all $n = ...
0
votes
3answers
36 views

induction help proving the sum of the n powers of 2

How do i prove using mathematical induction to prove that the sum of the firstn powers of 2 that can be computed by Evaluating function m(n) = $2^n -1$. $\sum_{k=0}^{n-1}2^k=1+2+4+...+2^{n-1} = ...
2
votes
2answers
41 views

To prove $m$ is not a square of a natural number

Let $m$ be a natural number with digits consisting if only $6$'s and $0$'s p. Prove that $m$ is not the square of a natural number.
1
vote
1answer
25 views

List results of exponentiation, with natural bases and exponents

I am looking for a way to construct an ordered set like $\{2^3, 2^4, 3^3, 2^5, 2^6, 3^4, 5^3, 2^7...\} = \{8, 16, 27, 32, 64, 81, 125, 128...\}$ Preferably, but not necessarily, with all bases ...
3
votes
1answer
67 views

Proving that nth derivate of $x e^{-x}$ is $(-1)^n (e^{-x})(x-n)$ by induction.

I'm quite stuck on this. How would you prove that the $n^{th}$ derivative of $x e^{-x}$ if the $(-1)^n (e^{-x})(x-n)$ by induction? I did: $\frac{d}{dx}(x e^{-x})=(e^{-x}) - x(e^{-x})$ Now I have ...