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

3
votes
2answers
99 views

Determinant involving recurrence

Evaluate $$\left| A \right| = \left| {\matrix{ {x + y} & {xy} & 0 & \cdots & \cdots & 0 \cr 1 & {x + y} & {xy} & \cdots & \cdots & 0 \cr 0 ...
2
votes
1answer
20 views

Proof Concerning Linear Independence And Maximal Subsets

Serge Lang's Linear Algebra has, in chapter 1, a proof which seems rather long-winded. He wants to prove the following theorem: Theorem 3.1. let V be a vector space over the field K. Let ...
0
votes
1answer
36 views

Proof by induction and inequalities

I am stuck on this question: given $a_1a_2≤(\frac{a_1+a_2}{2})^2$ prove by induction of m that $$a_1a_2...a_p≤(\frac{a_1+a_2+...+a_p}{p})^p$$ where $a_i$ are all positive and real and $p=2^m$ (an ...
0
votes
2answers
43 views

Vacuous truth and (simple and complete) induction

The way I understand complete induction, as applied to the naturals at least, the inductive step consists of assuming that a given proposition $p_i$ is true for $1 \le i \le n$, and from this deduce ...
0
votes
3answers
54 views

In proof by induction, what does it mean when condition for inductive step is lesser than the propsition itself?

My question is regarding the question posed at the end of the proof. My answer is that the result does not hold for all $m \ge 7$ because when $m=7$, the result is $343 \le 128$, which is false. ...
2
votes
2answers
188 views

Mathematical Induction Matrix Example

I'm a little rusty and I've never done a mathematical induction problem with matrices so I'm needing a little help in setting this problem up. Show that ...
4
votes
2answers
38 views

using the induction technique to prove $\Pi_{i=1}^{k}(2i-1)=\frac{(2k)!}{(k!)2^k}$

$\Pi_{i=1}^{k}(2i-1)=\frac{(2k)!}{k!2^k}$ clearly the products are in the set of the natural numbers. Step one show that P(1) is true $2(1)-1=1$ True. Step 2 induction assumption ...
0
votes
1answer
33 views

Base case in the Binet formula (Proof by strong induction)

I don't understand why the author says that the inductive formula does not apply until $u_3$. The formula does not depend on other terms in the Fibonacci sequence, so I thought I could just prove it ...
3
votes
2answers
51 views

Proving $\sum_{i=1}^{n}(i)(i!)=(n+1)!-1$ using induction

$\sum_{i=1}^{n}(i)(i!)=(n+1)!-1$ This proposition seem to be true First step $P(1)$ $1=2!-1$ Second step assume $P(k)$ $\sum_{i=1}^{k}(i)(i!)=(k+1)!-1$ Third step $P(k+1)$ The area of ...
1
vote
1answer
43 views

Check workings for Strong Induction (Proof by Contradiction)

I want to prove the following: Suppose that $P(n)$ is a statement involving a general positive integer $n$. Then $P(n)$ is true for all positive integers $n$ if: i) $P(1)$ is true, and ...
1
vote
1answer
54 views

How to use mathematical induction with inequality?

I am stuck with this question. Given that $n$ is a positive integer where $n≥2$, prove by the method of mathematical induction that (a) $$ \sum_{r=1}^{n-1} r^3 < \frac{n^4}{4} $$ (b) $$ ...
2
votes
1answer
44 views

What is the most elementary proof of these inequalities?

Let $p$ be a non-zero integer, and let $x_1$, $\ldots$, $x_n$ be $n$ positive real numbers. Then we define the $p$-th power mean $M_p$ of these numbers as $$ M_p \colon= (\frac{x_1^p + \ldots + ...
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
55 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
52 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
39 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
77 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
16 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
44 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
24 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
141 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
50 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
33 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
48 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
40 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
19 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
84 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
0answers
39 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
38 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
45 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
23 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
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 ...