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 aimed ...

learn more… | top users | synonyms

0
votes
0answers
46 views

Proof by Induction for Fundamental Thm of Arithmetic

Use induction to make our proof of the Fundamental Theorem of Arithmetic more rigorous. Recall that $p$ is prime iff for all $a,b\in\mathbb Z:p\mid(ab)$ implies $p\mid a$ or $p\mid b$. Prove that ...
2
votes
1answer
40 views

induction proof of recursive multiplication

mul(a,0) = 0 mul(a,n) = if a%2 then mul(2a,n/2) else mul(2a, (n-1)/2)+a mul(a,n) = a*n
1
vote
3answers
74 views

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ [duplicate]

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ How would you do the inductive step for this proof? I have the base case done.
0
votes
5answers
92 views

Use induction to show that $3^n >n^3$ for $n≥4$

Use induction to show that $3^n >n^3$ for $n≥4$. (Note that you have to start at $n=4$ as the result isn't true for $n=3$ !) I am very new to using induction, but as I understand it I have ...
3
votes
1answer
60 views

Do I need to use induction to have sufficient rigor in this proof?

I'm taking my first analysis class this summer. The professor asked us to prove that $a^{2n}-b^{2n}$ is divisible by $a+b$. After dorking around with the first couple of $n$ I was able to come up ...
0
votes
1answer
114 views

Find count of all combination of numbers whose sum is x

I want to find the sum of all combination of numbers whose sum is x, for e.g. when x = 3 f(x) = countOf(111,12,21,3) = 4
1
vote
4answers
54 views

Quick induction proof

I am trying to prove $n^3<n!$ for all integers $n\geq 6.$ It would be trivial to do this by induction if $(n+1)^3<(n+1)n^3$ holds. I looked this up, and I found this is true for integers $n\geq ...
1
vote
3answers
39 views

How is derived the inductive step in mathematical induction?

I am quite familiar with the algorithm of mathematical induction but I can't rationalize the inductive step very well. Suppose I have the classical example: $$0 + 1 +2 + \ldots + n = ...
0
votes
1answer
44 views

How to proof this: (m is odd ∧ n is odd)⇒ m + n is even

I don't quite understand why I can not proof the following: Assume that n,m ∈ N. Show: (m is odd ∧ n is odd)⇒ m + n is even. With this: Say n, m are odd. Then the remains of (m + n) / 2 is equal to ...
1
vote
3answers
20 views

Basic Induction Problem

For $N \geq 4$, prove $2^N \geq N^2$. I have the base case, $N=K$, and $N=K+1$ steps, but I am stuck at this point... $2^K\cdot 2 \geq (K+1)^2$ Thanks!
1
vote
2answers
31 views

Induction with negative step

We've learned that we can use induction to show that a statement holds for all natural numbers (or for all natural numbers above n). The steps are: prove that the statement holds for a base number b ...
2
votes
3answers
50 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
55 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
68 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
28 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
83 views

Proof by induction that $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ [duplicate]

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 ...
3
votes
1answer
46 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
36 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$ ...
1
vote
2answers
89 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
244 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
79 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
38 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
42 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
57 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
23 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
4k 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
43 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
59 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
31 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
40 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 ...
1
vote
4answers
108 views

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

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
76 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
40 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
27 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
75 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
63 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
38 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
61 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
27 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
76 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
337 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
51 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
108 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
75 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
62 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
147 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
134 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
120 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
38 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 ...