For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

learn more… | top users | synonyms

1
vote
1answer
15 views

Trouble proving through induction after establishing a basecase

What is the following sum? $\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3\cdot 4} + ... + \frac{1}{(n-1)n}$ Experiment, conjecture the value, and then prove it by induction. I found the sum ...
0
votes
0answers
22 views

Classical proof that well-ordering principle is equivalent to complete induction [duplicate]

I want to prove that: Well ordering principle ⟺ Complete Induction. I am interested in both directions of the implication. That is, that if every non-empty set contains a least element then if a ...
0
votes
1answer
472 views

Induction to prove regular expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
6
votes
1answer
463 views

Structural Induction vs Normal (Mathematical) Induction

In computer science and semantics I have come across structural induction many times. In that context, it is often presented as something different from but similar to mathematical induction, ...
18
votes
6answers
3k views

Why doesn't induction extend to infinity? (re: Fourier series)

While reading some things about analytic functions earlier tonight it came to my attention that Fourier series are not necessarily analytic. I used to think one could prove that they are analytic ...
11
votes
6answers
1k views

Why do we do mathematical induction only for positive whole numbers?

After reading a question made here, I wanted to ask "Why do we do mathematical induction only for positive whole numbers?" I know we usually start our mathematical induction by proving it works for ...
0
votes
1answer
39 views

Multiplication of two successive Fibonacci numbers [duplicate]

Recall the Fibonacci function defined by $f(0) = 0; \\f(1) = 1; \\f(n) = f(n-1) + f(n -􀀀 2)$ for all $n \ge 2$ Prove that $f(n) \cdot f(n + 1) = f(1)^2 + f(2)^2 + . . . + f(n)^2.$
1
vote
1answer
45 views

Recursion for strings.

Write a recursive procedure to compute the number of strings from $\{A, C, T, G\}$ of length $n$ that do not have $2$ consecutive $A$’s.
1
vote
1answer
55 views

Prove by mathematical induction.

TO BE PROVED: $$ \frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\dots \frac{1}{n^2}<2 $$ Please prove this by mathematical induction only. My approach: I already proved it through graphs but i have to ...
0
votes
2answers
29 views

Induction Help: prove $2n+1< 2^n$ for all $n$ greater than or equal to $3$.

I understand that he expanded the left side but I'm having trouble figuring out what he did on the right side of the inequality. Where the did the $2$ (in circle) come from?
0
votes
1answer
21 views

Prove regular expression with induction

I need help proving the following regular expression via induction. I have the base case (easy of course) but I'm having a difficult time determining the inductive case. A regular expression over ...
4
votes
2answers
72 views

$\frac{1\cdot2^2+2\cdot3^2+\cdots+n(n+1)^2}{1^2\cdot2+2^2\cdot3+\cdots+n^2(n+1)}=\frac{3n+5}{3n+1}$ by Mathematical Induction

Prove by Mathematical Induction: $$\frac{1\cdot2^2+2\cdot3^2+\cdots+n(n+1)^2}{1^2\cdot2+2^2\cdot3+\cdots+n^2(n+1)}=\frac{3n+5}{3n+1}$$ Now by inductive hypothesis: ...
2
votes
3answers
31 views

Probability of an even number of sixes

We throw a fair die $n$ times, show that the probability that there are an even number of sixes is $\frac{1}{2}[1+(\frac{2}{3})^n]$. For the purpose of this question, 0 is even. I tried doing ...
24
votes
1answer
40k views

What's the difference between simple induction and strong induction?

I just started to learn induction in my first year course. I'm having a difficult time grasping the concept. I believe I understand the basics but could someone summarize simple induction and strong ...
8
votes
9answers
2k views

What do we actually prove using induction theorem?

Here is the picture of the page of the book, I am reading: $$P_k: \qquad 1+3+5+\dots+(2k-1)=k^2$$ Now we want to show that this assumption implies that $P_{k+1}$ is also a true statement: ...
3
votes
0answers
45 views

Structural induction proof

I am trying to solve the following problem, please help me to complete the proof: I need to find the relation between the number of comas in a term $p_c$ of language L = {f,g} and the number $p_f$ of ...
1
vote
1answer
47 views

How many maps can exist between two sets?

I'm working on the following exercise. Why does the solution omit applying induction on $n$? That is, assume $P(n)$ and then use that assumption to prove $P(n + 1)$.
0
votes
0answers
54 views

Differentiate a geometric sum and show that it is less than an equation

The question: a) Differentiate both sides of the geometric series with respect to $r$: $$~~\displaystyle\sum_{i=0}^nr^i=\frac{1-r^{n+1}}{1-r}$$ b) Use the result in part (a) to show that (Assume ...
-1
votes
1answer
37 views

Is my proof by induction correct?

If $x_1 , x_2,......x_n$ are non-zero elements of a field so is $\prod_{k=1}^n x_k$; and $\left(\prod_{k=1}^n x_k\right)^{-1} = \prod_{k=1}^n x_k^{-1}$. Assume $n = 2$ true; How I did it: First: ...
0
votes
0answers
19 views

Proof by Induction for Recurrence Relations

I've been trying to work through this proof as an example problem in some lecture material and I want to confirm that my thought process is correct. Here is the problem: $\ T(n) = 2T(n/2)+2n, T(1) = ...
0
votes
2answers
43 views

Prove that $\frac{(a+1)^k}{a^k+1} \leq 2^{k-1}$

if $ k \geq 0$ Prove that $\frac{(a+1)^k}{a^k+1} \leq 2^{k-1}$ Proof (induction) let k = 1 then $$\frac{(a+1)^1}{a^1+1} \leq 2^{1-1}$$ , implies that $$ 1 \leq 1$$ so p(1) is true. Inductive step ...
0
votes
1answer
470 views

Prove through structural induction that a binary tree has an odd number of nodes

A full binary tree is a binary tree where every node has either 0 or 2 children. Prove that every non-empty full binary tree has an odd number of nodes. I dont know how to get started with this ...
1
vote
7answers
72 views

Proving $\frac{n}{n+1} < \frac{n+1}{n+2}$ by induction?

I have the inequality $\frac{n}{n+1} < \frac{n+1}{n+2}$ I'm not sure how to go about proving it. I've started by testing with n = 1, which results in $\frac{1}{2} < \frac{2}{3}$ which is true ...
0
votes
2answers
53 views

Proof that $\lfloor x + x\sqrt3 \rfloor = x + \lfloor x\sqrt3 \rfloor$ Where $x \in N$

I'm not sure if this is true or not. I was going to prove it via induction. Here is what I have so far. Base Case (x=0): $\lfloor 0 + 0\rfloor = 0 = 0 + \lfloor 0 \rfloor$ Induction Hypothesis (IH): ...
0
votes
1answer
35 views

Any collection of n coins can be obtained using a combination of 3¢ and 5¢ coins where n ≥ 14

I am trying to prove this statement with strong induction, but I'm a little lost on the inductive step. Proposition: Let P(n) be the sentence ‘any collection of n coins can be obtained using a ...
0
votes
2answers
59 views

Finding an expression for the sum of n tems of the series $1^2 + 2^2 + 3^2 + … + n^2$ [duplicate]

Possible Duplicate: why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$ I know that if you have a non-arithmetic or geometric progression, you can find a sum $S$ of a ...
6
votes
1answer
181 views

Formula for cos(k*x)

I need to prove that: \begin{align} c_k =&\; \cos(k\!\cdot\!x)\\ c_k :=&\; c_{k-1} +d_{k-1}\\ d_k :=&\; 2d_0\!\cdot\!c_k +d_{k−1}\\ d_0 :=&\; −2\!\cdot\!\sin^2{(x/2)}\\ \end{align} ...
6
votes
5answers
117 views

Prove by mathematical induction: $\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{n^2}>1$

Could anybody help me by checking this solution and maybe giving me a cleaner one. Prove by mathematical induction: $$\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{n^2}>1; n\geq2$$. So after I check ...
9
votes
4answers
222 views

Proving that $\frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{2n}>\frac{13}{24}$ by induction. Where am I going wrong?

I have to prove that $$\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{2n}>\frac{13}{24}$$ for every positive integer $n$. After I check the special cases $n=1,2$, I have to prove that the given ...
1
vote
1answer
40 views

Absolute value of product is less than product of absolute values: $|(1+a_1)(1+a_2)\dots (1+a_n)-1|\leq (1+|a_1|)(1+|a_2|)\dots (1+|a_n|)-1$

For a sequence $a_n\in\mathbb{C}$ I want to show that $$|(1+a_1)(1+a_2)\dots (1+a_n)-1|\leq (1+|a_1|)(1+|a_2|)\dots (1+|a_n|)-1$$ I think I should show this by induction on $n$. For the base case I'm ...
1
vote
2answers
48 views

Is my proof of the principle of backward induction using well-ordering correct?

I'm trying to prove backward induction, which I'll state as follows: Consider the set $\mathsf{A}$, where $n\in{\mathsf{A}}$, and $m+1\in{\mathsf{A}}$ $\implies$$m\in{\mathsf{A}}$. Then ...
3
votes
1answer
48 views

Require assistance proving $n≥2 \Longrightarrow \frac{n!}{n^n} ≤ \frac{1}{2}^{\lfloor \frac{n}{2}\rfloor}$

Theorem: $n≥2 \Longrightarrow \frac{n!}{n^n} ≤ \frac{1}{2}^{\lfloor \frac{n}{2}\rfloor}$ Attempted Solution: We use induction. Additionally, we prove the stronger inequality omitting the floor ...
1
vote
2answers
50 views

Proof by induction: $(a+b)^n=a^n+na^{n-1}b+\frac{n(n-1)}{2!}a^{n-2}b^2+…+nab^{n-1}+b^n$

I'm studying in preparation for a Mathematical Analysis I examination and I'm solving past exam exercises. If it's any indicator of difficulty, the exercise is Exercise 1 of 4, part $a$ and graded for ...
0
votes
3answers
54 views

Prove $n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0

The statement I'm trying to prove is: $n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0 I eventually need to prove $(k + 1)^3 + 7(k + 1) + 3$ is divisible by 3. I don't really understand ...
0
votes
5answers
127 views

Mathematical Induction problem

Can somebody help me with these questions? I can't seem to get started... Having $P(n) : n^2 + 5n + 1\text{ is even}$. a) Demonstrate that if $P(k)$ is True to some $k$ natural, then $P(k + 1)$ is ...
0
votes
0answers
28 views

Problem with induction [closed]

Prove by induction that given non-negative real numbers $a_1, a_2, a_3, ..., a_n$ ($a_i \ge 0$ for any $i \ge 1$), the folowing inequality is true for $n=1,2,3,...$ $$\prod_{i=1}^n(1 + a_i) \ge 1 + ...
0
votes
0answers
26 views

Solve the Recurrence Relation to Get a Theta Bound

If I have $T(n)=T(n-5)+n$, how would I go about using induction to find a $\Theta$ bound for this. I was able to use a tree method to get that the bounds should be about $\frac{n^2}{5}$, but I am ...
-1
votes
5answers
38 views

Divisibility by 101; a problem with induction [closed]

I was trying to show that $10^{2n}+(-1)^{n+1}$ is divisible by $101$. Would anyone help me with the induction step please?
1
vote
1answer
24 views

Proving Multiplicity in Polynomials with derivatives.

After learning multiplicity in polynomials we were given the task of proving that: if $ f(\alpha) = f'(\alpha) = f''(\alpha) = f'''(\alpha) =$ .... $f^{k-1}(\alpha) = 0$ and $f^{k}(\alpha) \not= 0$ ...
1
vote
4answers
52 views

Show that for each $n \geq 2$, $\left(1 - \frac{1}{4}\right)\left(1 - \frac{1}{9}\right) \cdots \left(1 - \frac{1}{n^2}\right) = \frac{n + 1}{2n}$ [duplicate]

Need to show that for each $n \in \mathbb{N}$, with $n \geq 2$, $$\left(1 - \frac{1}{4}\right)\left(1 - \frac{1}{9}\right) \cdots \left(1 - \frac{1}{n^2}\right) = \frac{n + 1}{2n}$$ How to start the ...
1
vote
1answer
25 views

How does this result follow?

In my real analysis text, an example of proof by induction is given by proving that for any real $x\ge 0$ and all integers $n\ge 0$ $$(1+x)^n \ge 1+nx+\frac {n(n-1)}2x^2$$ I can follow and understand ...
0
votes
3answers
26 views

The basis step is confusing, Prove by mathematical induction that $3 | (n^3 - n)$ for every positive integer n.

So I have an answer.. but the basis step doesn't make any sense to me. It is possible that I do not understand the syntax used. Let $P(n)$ be the predicate $3 | (n^3 - n)$ for every positive ...
1
vote
1answer
1k views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
6
votes
1answer
84 views

A Increasing Multiplicative Functional Equation where $nm$ is a cube

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $mn$ is a perfect cube. ...
0
votes
1answer
29 views

Is This Mathematical Induction?

Mathematical induction Follows Thus: $1.$ The basis (base case): prove that the statement holds for the first natural number $n$. Usually, $n = 0$ or $n = 1$. $2.$ The inductive step: prove that, ...
0
votes
3answers
33 views

Prove by induction that $36,306,3006,30006$ is divisible by 18

Hi I'm quite new to induction so I don't really know how I should tackle this problem. I took out a calculator and checked the results 2,16,167,1667 I sort of see a pattern but how would I start the ...
1
vote
0answers
31 views

Regarding the number of isomorphisms between splitting fields

Let $\phi : F \rightarrow F_1$ be an isomophism of fields and $f(x) > \in F[x]$. Let $\Phi : F[x] \rightarrow F_1[x]$ be the unique ring isomorphism which extends $\phi$ and maps $x$ to ...
1
vote
1answer
17 views

Inductive factorial formula proof - can't figure out how to finish proof

I am reading The Algorithm Design Manual and in the induction section of the first chapter, I am struggling to figure out how you go from one line to another in the final proof. Here is a picture of ...
0
votes
1answer
93 views

Proving by induction that a balanced strings of parentheses has equally many opening and closing parentheses

In computer science, a string is a finite sequence of characters. For strings $A$ and $B$, we express $AB$ as $A$ followed by $B$. A balanced string of parentheses is a string of open and closed ...
0
votes
1answer
21 views

Prove the arithmetic-geometric inequality for integers $n$ that are powers of two, i.e. $n=2^k$.

Prove the AG inequality for integers $n$ that are powers of two, i.e. $n=2^k$. Suppose $a_1,a_2,\dots,a_n>0$. The arithmetic mean of these numbers is $$\frac{a_1+\dots+a_n}{n}.$$ The geometric ...