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

23
votes
5answers
2k views

What makes induction a valid proof technique?

What makes induction (over natural numbers) a valid proof technique? Is $$ \dfrac{ P(0) \quad \forall i \in \mathbb{N}. P(i) \Rightarrow P(i+1) }{ \forall n \in \mathbb{N}. P(n)} $$ just taken for ...
2
votes
0answers
78 views

Can I use the equality $\phi^2=\phi+1$ without proving it?

I am looking at the following exercise: $$\text{ Show with induction,that the } i^{th} \text{ number Fibonacci satisfies the equality: } $$ $$F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$$ where $\phi$ ...
1
vote
3answers
69 views

Infinite descent method and strong induction

I encountered the following statement of the infinite descent principle (PID): PID. Let $p(n)$, $n \in \mathrm{N}$, be an arbitrary property of natural number $n$. Assume that (e) $p(1)$ is ...
1
vote
0answers
63 views

Prove: $a^m\cdot a^n \cdot a^p=a^{m+n+p}$

How can I prove the following: Prop.: let be $m,n,p \in \Bbb{N}$ and $a \in \Bbb{R}$ then $$a^m\cdot a^n \cdot a^p=a^{m+n+p}$$ ??? I thinked by induction and I must prove: 1) $a^0\cdot a^0 \cdot ...
0
votes
1answer
60 views

am i cheating in this number theory proof?

the question (from burton's elementary number theory); $verify\ that\ \forall n\ge 1,$ $$2\cdot6\cdot10\cdots(4n-2)=\frac{(2n)!}{n!}$$ my work/proof; this is obviously true for $n=1$, so assume ...
6
votes
4answers
281 views

The largest integer less than $n$ is $n-1$

Let $n$ be a positive integer. Prove that the largest integer which is less than $n$ is $n-1$. Attempt of a solution: Since $n$ is a positive integer $n>0$. I think I have to use the well-ordering ...
0
votes
2answers
45 views

Prove that $n<(3/2)^n$ for any $n$ with induction [closed]

need help with induction with inequality, I suck at it. $n<\left(\frac{3}{2}\right)^n$ for any $n$
0
votes
1answer
41 views

Inductive proof of inequality $a\le ab$ for nonnegative integers

I reading about of proof of the claim "If $a \ge 0$ and $b > 0$, then $a \le ab$. (Here $a$ and $b$ are integers.) The proof the author is employing is inductive. I understand the basis case; ...
-1
votes
1answer
25 views

Inductive Proof Algorithm

so I'm working on an algorithms assignment and am having a tough time understanding what to do: The equation is: $$T(n) = 2T(n/4) + n = \Theta(n) = O(n)$$ Right now I have gotten this far: $$T(1) = ...
3
votes
3answers
52 views

Prove that $2n+1 \leq 2^n$ for $n \geq 3$ using mathematical induction.

Question: $2n+1 \leq 2^n$, for all $n \geq 3$ I've tried: Basis: $P(3) = 7 \leq 8 $, so basis step is valid Pick an arbitrary value from the universe, $k \geq 3$ Inductive Step: $2k + 1 \leq ...
1
vote
2answers
56 views

How can I show that $n^{n+2}<(2n)!$ for any integer $n$.

When I was try to show that the series $\sum_n \frac{n^n}{(2n)!}$ is convergent using comparison test, I stuck at the point $n^{n+2}<(2n)!$ I think it can be show using mathematical induction. If ...
2
votes
1answer
34 views

is my induction proof sufficient?

question; prove that $\forall\ n\ge4, n\in \mathbb{Z}, \ n!\gt n^2$. my work; let $n=4$ then $4!=24 \gt 4^2=16.$ true. now assume $n! \gt n^2$ is true for all $n\le k$ so now assume $k! \gt ...
3
votes
5answers
614 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
1
vote
2answers
39 views

graph theory: show that for k=4 hesse diagram is not a planar graph

In this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$ For the set $A$ with $k$ elements, $k>0$ look at the diagram as a graph, it's vertices are the members of $P(A)$ ...
0
votes
1answer
167 views

Proof completion: if $Y$ is a closed term in strong nf, then $Yx$ weakly reduces to a strong nf $Z$

I am self-studying Hindley & Seldin's Lambda-Calculus and Combinators. I would appreciate some help with filling in a final detail for a proof for the following statement regarding combinatory ...
0
votes
2answers
31 views

Discrete Maths - Induction

I am having difficulty answering the following question: Can anyone show me how to solve this? I understand that I should be putting in a + 1 somewhere to simulate the next step, but I'm not sure ...
0
votes
2answers
73 views

Mathematical Induction Problem with Fraction

$$(3n-2)^2=\frac{n(6n^2-3n-1)}{2}$$ I can't seem to solve it out to the point where I can prove it right or wrong. I always hit some sort of roadblock where I don't have enough info to prove it ...
4
votes
2answers
34 views

Proving Induction $(1\cdot2\cdot3)+(2\cdot3\cdot4)+…+k(k+1)(k+2)=k(k+1)(k+2)(k+3)/4$

I need a little help with the algebra portion of the proof by induction. Here's what I have: Basis Step: $P(1)=1(1+1)(1+2)=6=1(1+1)(1+2)(1+3)/4=6$ - Proven Induction Step: ...
2
votes
1answer
28 views

Question on Induction (Very Simple)

I've just started a course in mathematics at university, and our current topic is mathematical induction. I've been given the following question: $$1+4+4^2+....+4^{n-1}=\frac{4^{n}-1}{3}.$$ I get ...
1
vote
1answer
44 views

scheme for n-dimensional induction

In slides: http://www.mathdb.org/notes_download/elementary/algebra/ae_A2.pdf I read the scheme for 2-dimensional induction, but Exists an scheme for n-dimensional induction? Thanks in advance!
0
votes
1answer
47 views

a finite induction question from burton's elementary number theory

this question comes from burton's elementary number theory, 4th edition. question 3 in 1.1 says to use the second principle of finite induction to establish that $$for\ all\ n\ge1,\ ^{(a)}\ ...
2
votes
6answers
280 views

Discrete math induction problem.

I am stuck at this step in the inductive process and I was wondering if someone can help me out from where I am stuck. Question: if $n$ is a positive integer, prove that, ...
0
votes
1answer
78 views

Spivak Chapter 2 Question 1 (i)

I don't understand Spivak's proof by induction of this exercise: Prove by induction $$1^2 + \ldots + n^2 = {n(n+1)(2n+1))\over 6}$$ It's true for $n = 1$ Then the proof continues adding $(k+1)^2$ ...
1
vote
1answer
89 views

How to proof (using by mathematical induction)($n\in \mathbb{N}$) [closed]

I would appreciate it if somebody could help me with the following problem: Q: How to proof (using by mathematical induction)($n=2,3,4,\cdots$) ...
0
votes
2answers
45 views

Induction inequality check

check my proof, I feel like I made a mistake :) so I'm looking to prove that when $p(n)$ is $n!<n^n$, $p(n)$ is true for all $n>1$. Base Case $$ p(2) \iff 2!<2^2 \iff 2<4 $$ Assume p(k) ...
2
votes
1answer
65 views

Use principle of mathematical induction to show a function defined recursively is uniquely determined.

I'm having difficulty with the following taken from "Elementary Number Theory And Its Applications" by Rosen section 1.1 questions. "Use the Principal Of Mathematical Induction to show that the value ...
3
votes
2answers
106 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
25 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
39 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
61 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
59 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
221 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
42 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
47 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
52 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
53 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
58 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
44 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
89 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
60 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
57 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} + ...
2
votes
1answer
88 views

Euler proof of the formula involving factorial?

Let me be formal and write the formula Euler's Formula: Let $a$ and $n$ be 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
154 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
98 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
18 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
47 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
45 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
29 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 = ...