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

5
votes
3answers
597 views

noetherian induction

So I think I've misunderstood the principle of Noetherian induction as stated in the Hartshorne exercise II.3.16, or his statement is slightly incorrect. He says: "Let $X$ be a Noetherian topological ...
4
votes
1answer
1k views

Explaining why a function is well-defined

How can I explain that a function is well-defined, if it's defined recursively by specifying $f(1)$, and a rule for finding $f(n)$ from $f(n-1)$? My reasoning: If the function for $f(n)$ can be ...
5
votes
5answers
287 views

Proving with Induction When The Claim Fails For Several Numbers

I want to find for what positive integers n, the statement $11n+17 \leq 2^n$ is true. I then want to prove that this is true with induction. The problem I see here, is that to prove it, I need to ...
3
votes
2answers
1k views

Using induction to extend DeMorgan's law

I have an assignment in my text that asks me to "Show how induction can be used to conclude that $(A_1 \cup A_2 \cup \dots A_n )^c = A_1^c \cap A_2^c \cap \dots \cap A_n^c$. The issue I am facing is ...
5
votes
2answers
160 views

Using induction on a sequence

I have a problem where I am asked to use induction to show that for the sequence defined as $x_1=1$, $x_{n+1}=\frac{3x_n+4}{4}$ the upper bound is $<4$. I was thinking of a following way. Assume ...
6
votes
4answers
210 views

Finding $A^n$ for a matrix

I have a matrix $$ A = \left[ {\begin{array}{cc} 1 & c \\ 0 & d \\ \end{array} } \right] $$ with $c$ and $d$ constant. I need to find $A^n$ ($n$ positive) and then need to prove ...
14
votes
5answers
821 views

What are some examples of induction where the base case is difficult but the inductive step is trivial?

According to Wikipedia: ...proofs by mathematical induction have two parts: the "base case" that shows that the theorem is true for a particular initial value such as n = 0 or n = 1 and ...
4
votes
12answers
358 views

Complete induction of $10^n \equiv (-1)^n \pmod{11}$

To prove $10^n \equiv (-1)^n\pmod{11}$, $n\geq 0$, I started an induction. It's $$11|((-1)^n - 10^n) \Longrightarrow (-1)^n -10^n = k*11,\quad k \in \mathbb{Z}. $$ For $n = 0$: $$ (-1)^0 - (10)^0 = ...
3
votes
3answers
81 views

Induction on logic formula

The term $((\bigvee_{i=1}^{n} p_i) \wedge (\bigwedge_{i=1}^{n} (p_i \to p)) \to p$ should be proven through induction. I'm relatively new to it, but I started with: basis: $p(1): (p_1 \wedge (p_1 \to ...
3
votes
1answer
558 views

Inductive proof for associative property in the propositional calculus

I'm not really used to inductive proofs at all but I have to proof the associative property in logic inductively, a general description is as followed: Is $A_l$ a left associative and $A_r$ a right ...
2
votes
2answers
134 views

Help on Inequality Proof

I'm trying to solve a proof for this inequality. I already have the solution, but have a question about the solution. Here's what I have so far: Prove $2^n > n^2$ for $n > 4$ Base Case $n=5$. $32 ...
0
votes
1answer
150 views

Expectation values, induction and conditioning

Suppose I have a series $X_t$ of random variables, $t \in \mathbb{N}_0$. I am not sure if the following reasoning is sound: Let $f(x)$ be a function of the random variables. Let $E[f(X_t)]$ denote ...
2
votes
3answers
196 views

Mathematical Induction (product of $n$ consecutive numbers)

Assumption: $$(n+1)(n+2) \cdots (2n) = (2^n)\cdot 1 \cdot 3 \cdot 5 \cdots (2n-1)$$ Prove for $n+1$: $$(n+2)(n+3) \cdots (2(n+1)) = (2^{n+1}) \cdot 1 \cdot 3 \cdot 5 \cdots (2(n+1)-1)$$ Using the ...
8
votes
3answers
367 views

Commutativity of multiplication in $\mathbb{N}$

I'm trying to prove that $a\cdot b=b\cdot a$ when $a$ and $b$ are two natural numbers. In the rest of this question I'm using $a'$ for the successor of $a$. Addition is defined as: $a+0=a$ ...
4
votes
2answers
269 views

Proof by Induction for inequality, $\sum_1^nk^{-2}\lt2-(1/n)$

Let n be a positive natural number , $n\ge 2$, then. $\displaystyle\sum_{k=1}^n \frac{1}{k^2} \lt 2 - \frac{1}{n}$ The basis step was easy but could someone give me a hint in the right direction ...
2
votes
1answer
202 views

Proof by induction: String of characters

Here is a question I've been working on and so far, can't get anything. Suppose we have a string which is recursively defined as: base case: A = F recursive case: ( A N A ) such as a string X = ...
7
votes
1answer
271 views

When can we say that a theorem has been proven?

I'm taking a Data Structures and Algorithms course for a CS program. The introductory material was all mathematics, mostly a series of formulas that we are to remember. I can work through the formulas ...
3
votes
2answers
304 views

Proof by induction: $\sum\limits_{i=1}^{n} \frac{1}{n+i} = \sum\limits_{i=1}^{n} \left(\frac{1}{2i-1} - \frac{1}{2i}\right)$

How can the following be proved by induction? $$\sum\limits_{i=1}^{n} \frac{1}{n+i} = \sum\limits_{i=1}^{n} \left(\frac{1}{2i-1} - \frac{1}{2i}\right)$$ I am out of ideas after practicing for a ...
0
votes
1answer
350 views

Inductive Definition on the set of strings

Given: $$ \Sigma = \{ a, b, c \}. $$ I am trying to give the inductive definitions of both the set of strings $\Sigma^*$ and $\Sigma^+$. Thank you.
5
votes
4answers
1k views

Geometric mean never exceeds arithmetic mean

This was a mathematical induction question proposed in a textbook, and I've exhausted multiple approaches (proving RHS - LHS > 0, splitting the fraction, fractional exponents, etc.) The geometric ...
1
vote
2answers
446 views

Proof by induction for systems of equations with arithmetic progression

A linear system of equations of the form $\begin{cases} ux+(u+d)y=u+2d\\ ax+(a+i)y=a+2i\end{cases}$ Will always have the solution $x=-1, y=2$ (easily proven through matrix algebra). How can I prove ...
1
vote
3answers
107 views

Solving linear recurrence by induction

Heres the "Link", my issue circled in red. Can anyone tell me how they get this this step?; How does $6s_k = 6(5^k-1)$? What rule are they using here? $s_{k+1} = 6s_k - 5s_{k-1} = 6(5^k ...
3
votes
1answer
170 views

Question about base cases in induction

So when first developing the natural numbers in basic set theory, most properties are proven by induction. This is very convenient since $\omega$ is the smallest inductive set. I saw a proof of the ...
3
votes
2answers
270 views

Induction problem: log of product equals sum of logs

Please help me prove by induction that $\displaystyle\forall n\in {{\mathbb{N}}^{*}}$, $\displaystyle\forall {{a}_{1}},\ldots ,{{a}_{n}}\in {\mathbb{R}}^{*}_{+}$, $\displaystyle \ln \left( ...
3
votes
3answers
334 views

Proof by induction: $\sum\limits_{i=0}^n i \cdot i! = (n+1)!-1$

Let n be a positive natural number , $n\ge 0$, then. $\displaystyle\sum_{i=0}^n i \cdot i!= (n+1)!-1$ Here is my attempt.I'm not going to write the base case because I understand that part. ...
4
votes
3answers
197 views

If $f(1) = 2$ and $f(n) = n \cdot f(n-1)$ then $f(n) \gt 2^n$ for all $n \gt 2$

I'm having a little difficulty in proving what are probably simple induction proofs. Here is the question. Define function $f(n)$ as follows. $f(1) = 2$ and $f(n) = n\cdot f(n-1)$ when $n > 1$. ...
3
votes
3answers
2k views

Proof by Strong Induction: every natural a product of an odd and a power of 2

Can someone guide me in the right direction on this question? Prove that every $n$ in $\mathbb{N}$ can be written as a product of an odd integer and a non-negative integer power of $2$. For ...
1
vote
2answers
79 views

Can I rewrite part of this induction?

Let $f_0 = 1$, and $f_1 = 1$, and $f_n = f_{n-1}+f_{n-2}$ when $n \gt 1$ (the Fibonacci sequence) Prove using induction that $f_n\gt 2n$, when $n \geq 6$. (note the $f_6 = 13$, $f_7=21$) I want ...
4
votes
6answers
2k views

Proving $(2n+1) + (2n+3) + \cdots + (4n-1) = 3n^{2}$ for all positive integers $n$

Prove $(2n+1) + (2n+3) + (2n+5) + \cdots + (4n-1) = 3n^{2}$ for all positive integers $n$. So the provided solution avoids induction and makes use of the fact that $1 + 3 + 5 + \cdots + (2n-1) ...
5
votes
3answers
563 views

Proof by induction for an exponential inequality

How do I prove $(2^r-1)(1-x)x^{2^{r}-2}+x^{2^{r}-1}>x^{2^{r}-r-1}$ for $\frac{1}{2}<x<1$ and $r \in \mathbb N$ $(r\neq 1)$?
6
votes
1answer
249 views

Is there a nice way to show that any finite sequence of arithmetic operations on the rationals can be put in 'standard form'?

I read a little proposition that any quantity obtainable from rational numbers by a finite number of operations $+$, $-$, $\cdot$, $\div$, $\sqrt{{}}$ can be put in a standard form $\frac{p}{q}\cdot ...
3
votes
2answers
559 views

$f_n$ is divisible by $4$ if and only if $n$ is divisible by $6$

I thought I had this question down, but while looking over my solution, I think I'm missing a step. I want to show for $f_n$ the nth fibonacci number, that $f_n$ is divisible by $4$ if and only if ...
3
votes
1answer
483 views

Question related with partial order - finite set - minimal element

Prove by induction. Every partial order on a nonempty finite set has at least one minimal element. How can I solve that question ?
2
votes
1answer
362 views

Use of algebra and factorials for a question related to proof by induction

$$ \begin{align*} &= (n+1)! − 1 + ( (n+1) · (n+1)! )\\ &= (n+1)! (1+n+1) − 1\\ &= (n+1)! (n+2) − 1\\ &= (n+2)! − 1\\ \end{align*} $$ I'm confused at how the first ...
3
votes
2answers
682 views

Proving insertion sort using induction

A while back when I was taking a first year cs course, our professor had us write the algorithm for insertion sort in The Scheme programming language. There were also several other similar recursion ...
1
vote
1answer
166 views

If $m < n$, then $k^m < k^n$?

For natural numbers, I would like to prove that if $m < n$, then $k^m < k^n$ for $k$ not $0$ or $1$. Induction seems viable, but I don't know which variable to induct on. Any suggestions?
2
votes
1answer
133 views

Stock Option induction problem

Can anyone help me solve this problem. I have no idea where to even start on it. Link inside stock option problem
3
votes
3answers
2k views

Proving that $|xy| = |x| + |y|$ being $x$ and $y$ two strings

I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$: $$ |xy| = |x| + |y| $$ with $x, y \in \Sigma^*$. To ...
7
votes
2answers
5k views

How do I prove this by induction? (sum of powers of 2)

How do I prove this by induction? Prove that for every natural number n, $ 2^0 + 2^1 + ... + 2^n = 2^{n+1}-1$ Here is my attempt. Base Case: let $ n = 0$ Then, $2^{0+1} - 1 = 1$ Which is true. ...
3
votes
2answers
140 views

Write the following sequence as a recurrence relation

Write the following sequence as a recurrence relation (with sufficient initial values specified): $$b_n=1-\frac{1}{2^n} \forall n\in\mathbb{N}^*$$ I think I am suppose to use induction (e.g. n-1) to ...
6
votes
2answers
285 views

Does the principle of mathematical induction extend to higher cardinalities?

Does the principle of mathematical induction extend to a cardinality larger than that of the countably infinite?
7
votes
3answers
883 views

Prove 7 divides $15^n+6$ with mathematical induction

Prove that for all natural numbers statement n, statement is dividable by 7 $$15^n+6$$ Base. We prove the statement for $n = 1$ 15 + 6 = 21 it is true Inductive step. Induction Hypothesis. We ...
6
votes
1answer
598 views

Proof by double induction on strings (SOLVED)

I am truly baffled as to go on to prove this by double induction: http://i.stack.imgur.com/Zvrzt.png (snap shot of question) This question seems rather trivial on first glimpse, however trying ...
18
votes
5answers
749 views

How does one actually show from associativity that one can drop parentheses?

I've always heard this reasoning, and it makes obvious sense, but how do you actually show it for some arbitrary product? Would it be something like this? ...
3
votes
1answer
155 views

Good resource of maths problems with solutions

I'm searching for a good book or web page that has a good amount of problems and their solutions, at undergraduate level, of divisibility, inequalities, induction, etc. Thanks in advance
2
votes
3answers
315 views

Can my proof be simplified and is it valid? $n(n+2) = (n+1)^2 - 1$ for all integers

I've decided to learn the basics of proofs and here is my first attempt. Could I improve or simplify my proof in any way? Is my formal language correct? Thanks! Let $n$ be any integer. $$n(n+2) = ...
29
votes
5answers
2k views

Dominoes and induction, or how does induction work?

I've never really understood why math induction is supposed to work. You have these 3 steps: Prove true for base case (n=0 or 1 or whatever) Assume true for n=k. Call this the induction ...
3
votes
4answers
696 views

demonstration by induction: $(1+a)^n ≥1+an$

Demonstrate by induction: $(1+a)^n ≥1+an$ is true, given a real number $a$, for any $n ∈ \mathbb N$. With $a > 0$ I need to demostre this using the induction principle. My doubt is in the second ...
33
votes
10answers
4k views

Good examples of double induction

I'm looking for good examples where double induction is necessary. What I mean by double induction is induction on $\omega^2$. These are intended as examples in an "Automatas and Formal Languages" ...
12
votes
2answers
3k views

What is complete induction, by example?

So, I've been revising for an exam and I came up against the question " prove $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$. Now, I know how to do this. If I assume $n=k$ divisible by $7$, ...