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
23 views

Proving i-th Fibonacci number by induction, can an inductive step be used for two sequential values?

I am working through the beginning of Introduction to Algorithms, and came across the problem Prove by induction that the $i$-th Fibonacci number satisfies the equality $$ F_{i} = \frac{\phi^{...
1
vote
1answer
44 views

Full binary tree proof validity: Number of leaves $L$ and number of nodes $N$

I'm working through the full binary tree proofs for a blog post I'm writing and I want to make sure I'm not missing anything. This particular proof focuses on relating the number of total nodes $N$ to ...
0
votes
0answers
44 views

Proof review - All natural numbers can be written as unique product of primes.

P(n): All natural numbers greater than 1 can be expressed as a unique product of primes where order doesn't matter. By strong induction: Base Case n=2: 2=2*1 so base case holds as this is a unique ...
1
vote
1answer
31 views

Determinant of $n \times n$ matrix whose entries are given by $m_{ij} = i^{n-j}$

Let $M_{n}$ denote the $n \times n$ matrix whose entries are given by $m_{ij} = i^{n - j}$, I believe that we have that $\det(M_{1}) = 1$ and $\det(M_{n}) = (-1)^{n-1}\cdot(n-1)! \cdot \det(M_{n-1})$ ...
1
vote
4answers
52 views

Derivative of degree k for $f(t)$ $=$ $1 \over {1 + t}$

Given $f: \Bbb R \setminus \{-1\} \rightarrow \Bbb R$, $f(t)$ $=$ $1 \over {1 + t}$, I would like to calculate the derivative of degree $k$. Approach First, we try to examine if ...
1
vote
3answers
80 views

Full binary tree theorem proof validity?

I'm reviewing some of the theorems that make up the Full binary tree theorem and want to make sure my proof for how the number of internal nodes $I$ is related to the number of total nodes $N$ is ...
2
votes
2answers
34 views

Induction Sum of all odd Numbers

Show that $\sum_{k=1}^{n}(2k-1)=n^2$ Beginning: n=1 $\sum_{k=1}^{1}(2k-1)=(2*1-1)=1=1^2$ Let $\sum_{k=1}^{n}(2k-1)=n^2$ be true, then for n=p+1 $\sum_{k=1}^{p+1}(2k-1)=(p+1)^2$ has to be true too....
4
votes
3answers
67 views

Pattern with the the tetration of summations.

While dealing with a question with finding an explicit form for a sequence I noticed something: $$\sum_{x_0=0}^{n-1} 1=\frac{n}{1!}$$ $$\sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} 1=\frac{n(n-1)}{2!}$$ ...
2
votes
2answers
65 views

Proving that $\frac{1}{4(5)}+\frac{1}{5(6)}+\frac{1}{6(7)}+\cdots+\frac{1}{(n+3)(n+4)}=\frac{n}{4(n+4)}$ by induction

I've proved the base case where $n=1$ and made the assumption that $n=k$ is true, but I'm stuck on the $n=k+1$ part. I just cannot seem to get the algebra to work in my favor. Here is the original:...
0
votes
0answers
48 views

Proof of propositional logic theorem using Induction on Formulas

How to prove the following theorem using induction on formulas? Let V and V' be two valuations of L. Let $\alpha$ be a formula such that V(p) = V'(p), for all atomic formula p that is subformula ...
2
votes
3answers
57 views

Counting the number of subsets of a set of 2n elements satisfying some conditions.

Let $X =\{v_1, v_2,\cdots, v_n, v_{n+1},\cdots, v_{2n}\}$ be a set of $2n$ elements. I want to find the number of subsets of $X$ with $n$ elements such that both $v_i$ and $v_{n+i} $ are not together ...
0
votes
1answer
22 views

Prove that the arithmetic-geometric mean inequality holds for any list of numbers whose length is a power of 2

I am self-studying and currently reading How to Prove it by Velleman. I tried to prove the above by induction (I proved that this holds true for $n=2$), but I think my proof is wrong. I only started ...
1
vote
2answers
46 views

Prove the n-th Fibonacci number is less than $2^n$ for all n greater than zero using strong induction

I need to prove the n-th Fibonacci number is less than $2^n$ for all $n \geq 0$ using strong induction. I have been exposed to the idea that strong induction differs from weak induction in that the ...
2
votes
2answers
99 views

Rebracketing Theorem

My questions regarding the below theorem Both questions are centred on Eq(2) and the paragraph preceding it. 1) How is it that Eq(2) contains $a_k$ but in that section of the proof the assumption is ...
2
votes
1answer
90 views

understanding a proof which uses induction on the length of a formula

This comes from Shoenfield's textbook Mathematical Logic. Here is the theorem and its proof: If $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators and $u_1\dots u_n$ and $u_1'\dots u_n'$ are ...
3
votes
0answers
51 views

Can you please comment on and check these couple of induction proofs?

So the following statements need to be proved: 1) $(1+a_1)(1+a_2)\cdots(1+a_n)>1+a_1+a_2+\cdots+a_n$ for $a_i>0,(i=1,2,\ldots,n)$ and $n\ge2$ 2) $(1-a_1)(1-a_2)\cdots(1-a_n)<1-(a_1+a_2+\...
0
votes
1answer
24 views

Prove if $x_1,…,x_n$ are natural numbers with $n\geq2$ then $x_1x_2…x_n$ is odd iff $x_i$ is odd for all $i$, $1\leq i\leq n$

I am not sure if Im on the right track here but if any one could help out I would greatly appreciate it. Prove if $x_1,...,x_n$ are natural numbers with $n\geq2$ then $x_1x_2...x_n$ is odd iff $...
2
votes
6answers
115 views

Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$

My question is: Prove by induction that $$3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$$ whenever $n$ is a nonnegative integer. I'm stuck at the basis step. If I ...
0
votes
0answers
35 views

How to get a feel for rigor/form used in mathematics?

I'm an engineer, and while you get introduced to many concepts of mathematics, but only with a subset of the vocabulary, and none of the rigor and proofs. So while trying to read a mathematical book, ...
4
votes
5answers
78 views

Inequality : $\displaystyle \sum_{k=1}^n x_k\cdot \displaystyle \sum_{k=1}^n \dfrac{1}{x_k} \geq n^2$

I have to show the inequality of $$\left(\sum_{i=1}^n x_i\right)*\left(\sum_{i=1}^n \frac{1}{x_i}\right) \geq n^2.$$For $x_1, ... x_n \in \mathbb{R_{>0}}$ and $ n \geq 1$. I wanted to show this ...
2
votes
1answer
38 views

Well-ordering principle and theorem

Could somebody clearly explain the difference between the well-ordering principle and the well-ordering theorem? Is one of these related to the Principle of Mathematical Induction, and the other to ...
0
votes
1answer
48 views

Fibonacci Sequence: Prove $f_1+f_3+\dots+f_{2n-1}=f_{2n}$ by Induction.

I believe the majority of my proof is correct I'm just not certain about the base case if any one can explain how to do that base case or fix any error I made I would greatly appreciate it. Recall ...
3
votes
2answers
27 views

induction proof over graphs

I have a question about how to apply induction proofs over a graph. Let's see for example if I have the following theorem: Proof by induction that if T has n vertices then it has n-1 edges. So what ...
0
votes
1answer
55 views

proof of an equivalence

I am trying to prove something by induction, and in induction step I had to prove this $$1+ \sum_{k=1}^{\lceil{\frac{n-1}{2}}\rceil} (-1)^{k}\frac{(t^2)^{2k}}{(2k)!} = \sum_{k=0}^{\lfloor{\frac{n}{2}}\...
2
votes
3answers
48 views

induction clarification about the step $n+1$

Suppose i need to prove that $\frac{1}{2^2}+\frac{1}{3^2}...+\frac{1}{n^2}<1-\frac{1}{n}$ So in the step of $n+1$, the right side becomes $<1-\frac{1}{n+1}$ or is it: $<1-\frac{1}{n}-\frac{1}...
2
votes
1answer
76 views

Strange Algebra

I am working on a mathematical induction worksheet and my professor gave us the key and I have run across something that makes zero sense to me so please explain if you can. Additional info: $k \ge2$ ...
3
votes
2answers
55 views

Prove that $\Gamma(-k+\frac{1}{2})=\frac{(-1)^k 2^k}{1\cdot 3\cdot 5\cdots(2k-1)}\sqrt{\pi}$.

I was able to prove that $$ \Gamma\left (k+\frac{1}{2} \right )=\frac{1\cdot 3\cdot 5\cdots(2k-1)}{2^k}\sqrt{\pi}.\tag{$k\geq 1$}$$ using the Legendre's duplication formula. But I can't do the same to ...
1
vote
4answers
83 views

Finding a closed form for $\sum^{n}_{k=1} \frac{k}{(k+1)!} $

I'm finding a closed form to $\sum^{n}_{k=1} \frac{k}{(k+1)!} (n \leq 1) $ (in a environment of induction and recurrence) I've been trying to solve it without success, can anybody help me (?) The ...
0
votes
2answers
60 views

Mathematical induction: $4 + 5 + 6 + … + n = \dfrac{n(n+1)}{3}$ where $(n \ge 4)$

Prove using mathematical induction that 4 + 5 + 6 + … + n = [n(n+1)] / 3 (n is an integer >= 4) I just wanted to confirm because my Base case P(4) is false. So this statement can't be proven?
3
votes
1answer
72 views

Need help with Knuth's proof for Gray Codes

I am reading Knuth's "The Art of Computer Programming" Volume 4 Fascicle 2A. Needless to say I am pretty poor in Mathematics and I need help understanding some of the proofs. If anyone has any ...
4
votes
2answers
74 views

Proving that $f_2+f_4+\cdots+f_{2n}=f_{2n+1}-1$ for Fibonacci numbers by induction

Given: $f_1 = f_2 = 1$ and for $n \in\mathbb{N}$, $f_{n+2} =f_{n+1} + f_n$. Prove that $f_2 + f_4 + \dots + f_{2n} = f_{2n+1}- 1$. Would you start with setting $f_2 + f_4 + \dots + f_{2n}= ...
3
votes
3answers
38 views

Using 4-cent and 11-cent stamps for postage (induction)

I was wondering how many base cases are needed and when to stop (in general). For example, I have 4-cent and 11-cent stamps and I need to determine the amount of postage I can make, the cases I have ...
1
vote
3answers
60 views

Proving that $3 + 3 \times 5 + 3 \times 5^2 + \cdots+ 3 \times 5^n = [3(5^{n+1} - 1)] / 4$ whenever $n \geq 0$

Use induction to show that $$3 + 3 \times 5 + 3 \times 5^2 + \cdots+ 3 \times 5^n= \frac{3(5^{n+1} - 1)}{4} $$whenever $n$ is a non-negative integer. I know I need a base-case where $n = 0$: $$3 \...
0
votes
2answers
20 views

Strong Induction issue

I am trying to prove a statement using strong induction but I seem to be getting stuck. I don't know if did something wrong or I am just not recognizing an opportunity for factoring/how to factor ...
3
votes
2answers
91 views

Prove that $(n!)^2 ≥ n^n$ using mathematical induction [duplicate]

1° $n_0=1$ $(1!)^2 \ge 1^1$ $1\ge1$ 2° $k \ge n_0$ assumption: $$(k!)^2 \ge k^k$$ and for k+1: $$((k+1)!)^2 \ge (k+1)^{k+1}$$ I also noticed that: $$((k+1)!)^2 = (k!)^2 * (k+1)^2$$
5
votes
2answers
67 views

Proving by induction that the sequence $a_{n+1}=\sqrt{3a_n-1}$ is increasing

$a_1=1$; $a_{n+1}=\sqrt{3a_n-1}$ $\quad$ $(n\ge1)$ Now I have to show it is true for $n=1$, which is easy. I have to assume it is true for $n=k$, therefore: $\sqrt{3a_{k}-1}$ $\gt$ $\sqrt{3a_{k-...
0
votes
3answers
58 views

Why do you need to show A(1) before proving A(n) by induction? [duplicate]

My instructor stated that in order to have a valid proof by mathematical induction, you first have to show A(1) holds, and then assume A(n) to deduce A(n+2). Why is the first step necessary if we are ...
3
votes
4answers
172 views

Prove if $n \in \mathbb N$, then $\frac{1}{2!}+\cdots+\frac{n}{(n+1)!}=1-\frac{1}{(n+1)!}$ [duplicate]

Prove if $n \in \mathbb N$, then $\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\cdots+\frac{n}{\left(n+1\right)!} = 1-\frac{1}{\left(n+1\right)!}$ So I proved the base case where $n=1$ and got $\frac{1}{2}...
3
votes
1answer
42 views

Double induction - another method?

I am going through some good old Fibonacci proof by induction problems that require two counters $m, n$ instead of one. In order to prove $P(m, n)$ for all $m,n \in \mathbb{N}$, I am thinking of ...
0
votes
1answer
48 views

What am I missing in this induction proof?

Prove that if $g:\mathbb{N}\rightarrow \mathbb{N}$ and $\forall x,y\in \mathbb{N}, x<y\Rightarrow g(x)<g(y)$ then $n\leq g(n)\space\space\space \forall n\in \mathbb{N}$ My proof so far (...
1
vote
0answers
31 views

Empty Twin Prime Sets

Consider this set of numbers: $1, 5, 8, 11, 13, 31, 37, 53, 61, 73, 79, 97, 122, 127$ This is the set of numbers $n$ such that $nm \pm 1$ is not a twin prime pair for all $m \leq n$. For instance, $...
1
vote
3answers
70 views

Proof by math induction with inequality example, why is “replacement” allowed?

I have trouble with the understanding of mathematical induction concerning inequalities. For example, the question is: Prove by mathematical induction that $ n ^ 2 <2 ^ n $ if $ \forall n \in {N}$ ...
0
votes
0answers
16 views

Prove that reverse of regular L is also regular [duplicate]

Prove that reverse of regular language is also regular. I know, how i can to this by using DFA of L. Changing directions of edges and so on. But how can it be done with Structural induction? What ...
0
votes
2answers
49 views

Is this type of proof by induction correct in Sylow's Theorem?

The following is the first part of the Sylow's Thm: My question is: if order of $G$ was $p^a$ (and not $p^am$) then we could start with $|G|=1$ which means $a=0$. Then supposed that the theorem ...
1
vote
6answers
84 views

Prove by induction the particular inequality $\left(1.3\right)^n \ge 1 + \left(0.3\right)n$ for every $n \in \mathbb N$

$\left(1.3\right)^n \ge 1 + \left(0.3\right)n$ for every $n \in \mathbb N$ Not sure where I'm going wrong in my Algebra, but I assume it's because I'm adding an extra term. Is the extra term ...
0
votes
1answer
47 views

Strong Induction for Fibonacci number related identity $f_{n-m} = f_{m}f_{n+1} + f_{m-1} f_n$ [closed]

Let $f_n$ be the $n^{th}$ Fibonacci number. Let $m$ be a fixed strictly positive integer. Prove by strong induction that for all $n\ge 0$, $$f_{n+m} = f_{m}f_{n+1} + f_{m-1} f_n$$ edit: $f_{n+m} = ...
1
vote
2answers
26 views

Set-Theoretic Probability

Consider $\{B_i | i \in I\}$ be a collection of events where $I$ is an arbitrary index set. I would like to show that $$\left(\bigcup_{i \in I} B_i\right)^c = \bigcap_{i \in I} B_i^c.$$ My friend ...
2
votes
0answers
61 views

Determinant of a block matrix $2n$ by $2n$

Consider the block $2n \times 2n$ matrix $$\begin{bmatrix} A&B\\ 0&D \end{bmatrix}$$ where $A,B,D$ are $n \times n$ blocks. Show that $$\det\begin{bmatrix} A&B\\ 0&D \...
1
vote
1answer
37 views

Induction problem for $U_{n+1}(x) = 2x U_n(x) - U_{n-1}(x),$ what can be assumed?

I have this straightforward induction problem that perhaps I am over thinking at this time of the morning. Here it is: $U_1(x) = 1, \; U_2(x) = 2x, \; U_{n+1}(x) = 2x U_n(x) - U_{n-1}(x).$ Prove ...
3
votes
0answers
39 views

Proof by “continuous induction”

There’s a method of proving inequalities over some interval of real numbers using differentiation. For instance to prove that $x-\log(1+x) \geqslant 0$ whenever $x \geqslant 0$ we can differentiate ...