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
1answer
39 views

Doing a proof by induction?

I am trying to perform this proof but I find myself stuck Prove for all natural number n. $\sum_{i=1}^{n}(3i-2)=\frac{n}{2}(3n-1)$ The first step ofcourse is P(1) because 1 is the first natural ...
1
vote
2answers
62 views

proof by induction that every non-zero natural number has a predecessor

I am trying to prove by induction that every non-zero natural number has at least one predecessor. However, I don't know what to use as a base case, since 0 is not non-zero and I haven't yet ...
0
votes
1answer
25 views

Analysis, prove a period by induction

Given that $F(x) = F(x+T)$ is $T$-periodic, prove by induction that $F(x) = F(x+nT)$ for all $n \in \mathbb N$. Would appreciate some help with this... one of my finals practice questions. Thanks.
0
votes
3answers
53 views

How to derive this inequality?

How to derive the following inequality for all positive integers $n \geq 2$? $$ \frac{n!}{n^n} \leq \left(\frac{1}{2}\right)^k,$$ where $k$ denotes the greatest integer less than or equal to $\dfrac ...
0
votes
2answers
40 views

How to derive these inequalities?

I can derive the inequalities $$ n^p < \frac{(n+1)^{p+1} - n^{p+1}}{p+1} < (n+1)^p $$ for any positive integers $p$ and $n$. These actually follow from the identity $$b^p - a^p = (b-a)(b^{p-1} + ...
1
vote
0answers
45 views

Euler proof of the formula for factorial?

Let me be formal and write the formula Euler's Formula: Let a and n by nonnegative integers with $a\geq n.$ Then $$n!=a^n-\binom{n}{1}(a-1)^n+\binom{n}{2}(a-2)^n-\binom{n}{3}(a-3)^n+ ...
3
votes
2answers
152 views

How Many Miles to Retrieve an Object N Miles into a Desert?

The problem: Suppose that you are interested in retrieving an object located in the middle of the desert, n kilometers away. Your car can carry enough fuel to travel 3 kilometers, and you have an ...
0
votes
3answers
82 views

Number Theory - Proof by Induction

Show that: $2903^n - 803^n - 464^n + 261^n$ is divisible by $1897$ for all integers $n\geq1$ using induction.
0
votes
0answers
17 views

Induction over DAGs

I'd like to prove a proposition true over all valid Directed Acausal Graphs. I think I can do that by starting with a graph with one node and adding either a new node and connection, or a new valid ...
2
votes
0answers
45 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}$$ which can be proved combinatorically whether one particular element(among the $n$) is ...
2
votes
1answer
42 views

Generalized Induction Verification

Consider the following simple exercise. Prove or disprove: $\gcd(km, kn) = k \gcd(m, n)$, where $m, n, k$ are natural numbers. Now, this is easy to prove using prime factorization. Knowing that ...
2
votes
1answer
26 views

Problems relating to fibonacci sequence via induction

Hey guys I have just started looking into induction and came across this problem regarding fibonnaci sequence that I don't quite know how to solve. The fibonacci sequence $\{f_n\}$ is defined by $f_0 = ...
1
vote
2answers
45 views

Use induction to show that $a_{n+1}-a_n=\biggl(-\frac{1}{2} \biggr)^n (a_1-a_0) .$

Let $a_0$ and $a_1$ be distinct real numbers. Define $a_n=\frac{a_{n-1}+a_{n-2}}{2}$ for each positive integer $n\geq 2$. Prove that $$a_{n+1}-a_n=\biggl(-\frac{1}{2} \biggr)^n (a_1-a_0) $$ ...
1
vote
1answer
53 views

Prove by induction $n^{n+1}>(n+1)^{n}$, for $n\geq3$

I got some question on how to proceed on the proof below, Prove that: $n^{n+1}>(n+1)^{n}$, for $n\geq3$ By induction: Inequality holds for $n=3$ , $3^4=81\geq 4^3 =64$. Suppose it holds for ...
1
vote
2answers
142 views

Finding a proof to the 'squares' problem

I am trying to find a proof for the general case of the solution to the 'Squares' Problem. This is what I have managed to figure out: If n is the number of squares in the top row, then the number ...
1
vote
1answer
53 views

How to prove a very basic algorithm by induction

I just studied proofs by induction on a math book here and everything is neat and funny: the general strategy is to assume the LHS to be true, and use it to prove the RHS (for the inductive step). Now ...
1
vote
1answer
34 views

How to prove by induction the constructibility of a line segment of length $\sqrt{n}$?

How to prove the following statement by induction? If a line of unit length is given, then a line of length $\sqrt{n}$ can be constructed with straightedge and compass for each positive integer $n$. ...
1
vote
1answer
32 views

Complete induction - is my proof valid?

I'm trying to get through Spivak's Calculus on my own and even though I kinda understand induction I'm not so sure that's the case when it comes to complete induction. So I tried to do a starred ...
2
votes
2answers
90 views

Proof by induction that $(1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2$

I'm sitting with the proof in front of me, but I do not understand it. $$A = \{n \in Z^{++} \mid (1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2\}$$ The first step of proof by induction is ...
1
vote
1answer
51 views

Proving Hermite's identity using induction

Can someone help me? This should be easy but I couldn't find it on any book or the internet. $$ \sum_{k=0}^{n-1}\left\lfloor x + \frac{k}{n}\right\rfloor = \lfloor nx \rfloor $$
1
vote
3answers
98 views

Prove by induction that $(n+1)^2 + (n+2)^2 + … + (2n)^2 = \frac{n(2n+1)(7n+1)}{6}$

Prove by induction that $$(n+1)^2 + (n+2)^2 + ... + (2n)^2 = \frac{n(2n+1)(7n+1)}{6}.$$ I got up to: $n=1$ is true, and assuming $n=k$ prove for $n=k+1$. Prove... ...
0
votes
3answers
41 views

Why does one modulus disappear when modded by another modulus?

I have the following equation: ( ((X + Y) mod 29) - Y) mod 29 = Z However, This can also be written as: ...
1
vote
1answer
68 views

Using $\sqrt{1-t}\leq 1-\frac t2$ to show that $\frac{1\cdot3\cdot5\cdots(2n-1)}{2\cdot4\cdot6\cdots2n}\geq\frac1{2\sqrt n}$

I have a problem that tells me to use that $\sqrt{1-t}\leq 1-\frac t2$ for $t\in(0,1)$ to show by induction that $\frac{1\cdot3\cdot5\cdots(2n-1)}{2\cdot4\cdot6\cdots2n}\geq\frac1{2\sqrt n}$ So far I ...
0
votes
0answers
42 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
22 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
62 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
85 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
53 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
43 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
-4
votes
1answer
48 views

Use mathematical induction to prove that the proposition is true [closed]

Use mathematical induction to prove that the proposition is true: $(x + 1)^n > 1 + x^n$; for $n\geq2$ and $x>0$;
0
votes
4answers
50 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
25 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
43 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
19 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
24 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
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
47 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
60 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
46 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
38 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
31 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
87 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
54 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 ...