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

4
votes
0answers
76 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
59 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
57 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 ...
7
votes
4answers
277 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
40 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
23 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
51 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
55 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
33 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
594 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
38 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
166 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
71 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
42 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
43 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
261 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
74 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
84 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
61 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
104 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
21 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
37 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
47 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
57 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
197 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
37 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
48 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
56 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
41 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
63 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
48 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
153 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
96 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
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
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
27 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) $$ ...