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

1
vote
0answers
19 views

Proving properties of closures using intersection of indexed sets and topology

How would I write a proof for this example? Let X be a set, and let $B \subseteq \mathcal P \left({X}\right)$. Define $B^* =${ $U \subseteq X:$ There is an index set $I$ and $U_{i} \in B$ for each ...
2
votes
1answer
13 views

Uniqueness in transfinite recursion.

Theorem of transfinite recursion: Given a well-ordered set $A$ let $\varphi(g,y)$ be a ZF formula such that for every $a \in A$ and every function $g$ with domain $I_a$ (where $I_a$ is the initial ...
1
vote
2answers
45 views

If $a_i>o$ then $(a_1a_2\cdots a_{2^n})^{1/2^n}\leq \frac{a_1+a_2+\cdots+a_{2^n}}{2^n}$

I need help to prove this inequality, I have no idea how to proceed with the inductive step: $$a_1,a_2,\ldots,a_{2^n}>0 \Longrightarrow(a_1a_2\cdots a_{2^n})^{1/2^n}\leq ...
1
vote
1answer
25 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ...
0
votes
1answer
40 views

Help to clarify inductive step for proof of $\mathbb{N_m} \rightarrow \mathbb{N}_n\Rightarrow m\le n$

The statement to prove is: If there exists an injection $\mathbb{N_m} \rightarrow \mathbb{N}_n$ then $m\le n$ The solution says to prove by induction on $n$. I just need help on the inductive ...
0
votes
5answers
48 views

Proof of $\forall n \in \Bbb N$, $n > 2 \implies n! < n^n$

What I've got so far is this: Base case: n = 3 then $3 *2 * 1 = 6$ and $3^3 = 27$ $\therefore 6 < 27, 3! < 3^3$ So the base case is true. So if we assume $n! < n^n$ (n > 2) $(n + 1)! = ...
1
vote
4answers
41 views

Prove $\forall n \in\Bbb N$, $0 < a < 1$ $\implies$ $a^n \leq 1$

I'm trying to prove this by induction but I'm running into some trouble. The base case is $0$, so, $a^0 = 1$, the inequality holds true Being new to induction, I don't exactly know what to do for ...
1
vote
1answer
30 views

Can someone explain the logic behind this step in a induction problem

There is a question in the book that I don't quite understand. Question Show that $n^2$ is smaller than $2^n$ whenever $n\ge5$. At the $k+1$ step it gets very whacked and confusing. $k+1$ ...
1
vote
1answer
35 views

Prove by Structural induction, circular permutations

Prove by Structural Induction: For a circular permutation of $n$ elements, the number of permutations is $(n-1)!$ How is this done?
0
votes
3answers
37 views

How do I reduce this induction problem at the k+1 step

Show that $2^n > n^2$ through induction and so far I got to the $k+1$ step, but I am stuck. I have $2^{k+1} = 2 +2^k$, but I don`t know how the book turned it into $k^2 +k^2$. The book then ...
2
votes
2answers
70 views

Better proof that $n \leq 2n$ for all natural numbers?

I tried proving via induction on naturals that $n \leq 2n$ for each natural $n$. Obviously, $0 \leq 2(0)$, and then assuming for any given $n$, $n \leq 2n$, you just show that $n + 1 \leq 2(n + 1).$ ...
1
vote
2answers
68 views

Proving inequality $3^{n^2} > (n!)^4$

Prove that $3^{n^2} > (n!)^4$ for all positive integers $n$. I tried to use induction on this problem but failed to do so. I instead tried to prove $3^{2n+1}>(n+1)^4$, but couldn't come up ...
0
votes
2answers
49 views

Proof by induction $\sum_{k=1}^{n}$ $k \binom{n}{k}$ $= n2^{n-1}$ for each natural number n [duplicate]

Prove by induction that $\sum_{k=1}^{n}$ $k \binom{n}{k}$ $= n2^{n-1}$ for each natural number n
0
votes
1answer
30 views

Induction proof involving sets

Suppose $A_1,A_2,...A_n$ are sets in some universal set $U$, and $n\geq2$. Prove that $\overline{A_1 \cup A_2 \cup ... \cup A_n}$ = $\overline{A_1} \cap \overline{A_2} \cap ... \cap \overline{A_n}$
1
vote
1answer
61 views

Proof by induction or strong induction [on hold]

I have to prove the following using induction or strong induction Suppose $a\in\mathbb{Z}$. Prove that $5 | 2^na$ implies $5 | a$ for any $n\in\mathbb{N}$.
0
votes
3answers
74 views

Lightbulb puzzle related to proofs by induction.

The puzzle question was as follows: There is a circle of $n > 2$ lights with a switch next to each of them. Each switch can be flipped between two positions, thereby triggering the on/off states of ...
2
votes
1answer
74 views

Mathematical Induction proof for $(n!)^2 > n^n$

I have the math problem (induction proof - $n!^2 > n^n$) that I try to solve and I haven't yet managed to get it right so maybe somebody could help me. My current plan solving the problem is the ...
2
votes
2answers
21 views

Proving arithmetic series by induction

How do I prove this statement by the method of induction: $$ \sum_{r=1}^n [d + (r - 1)d] = \frac{n}{2}[2a + (n - 1)d] $$ I know that $d + (r - 1)d$ stands for $u_n$ in an arithmetic series, and the ...
4
votes
1answer
84 views

How to prove Post's Theorem by induction?

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...
-1
votes
3answers
67 views

Prove by induction that $2^m-1>m^3$ [closed]

I have to prove that this inequality, for $m \geq 10$, using induction on $m$. Can anyone help me?
1
vote
2answers
43 views

Number of ways to write a natural as a sum of naturals [duplicate]

Problem: Let $n$ be a natural number, and $S(n)$ be the number of ways $n$ can be written as a sum of naturals. For instance, $S(3) = 4$ because $3 = 2+1 = 1+2 = 1+1+1$ and these are four different ...
3
votes
2answers
82 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
4
votes
1answer
58 views

how to solve this elementary induction proof

this is a seemingly simple induction question that has me confused about perhaps my understanding of how to apply induction the question; $$\frac{1}{1^2}+ \cdots+\frac{1}{n^2}\ \le\ 2-\frac{1}{n},\ ...
14
votes
3answers
1k 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 ...
3
votes
0answers
66 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
67 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
57 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
272 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
44 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
39 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
21 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
41 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
54 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
576 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
36 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
126 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
30 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
66 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
41 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
38 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
243 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
66 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
43 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
55 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
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 ...