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

Lines in the plane from Concrete Mathematics. How many bounded regions are there?

I'm studying Concrete Mathematics by Donald Knuth. While doing the warmup questions, from the recurrence chapter, I stumbled upon an interesting problem. I have an intuition about the solution but I ...
2
votes
2answers
47 views

Prove by Induction ( a Limit)

I think I did much wrong with this exercise... I think I solve it , in such case I'd like to know others way to solve... (Introduction to calculus and analysis vol 1, Courant page 113, exersice 16 ) ...
0
votes
2answers
25 views

proof by induction for golden ratio and fibonacci sequence

I have to prove the following equation by induction for $$x = \phi$$ I am stuck and I don't know how to proceed. This is the equation $$ \phi ^n = f_n\phi + f_{n-1} $$ where $f_n$ is the nth term ...
9
votes
6answers
350 views

Principle of Transfinite Induction

I am well familiar with the principle of mathematical induction. But while reading a paper by Roggenkamp, I encountered the Principle of Transfinite Induction (PTI). I do not know the theory of ...
3
votes
2answers
34 views

Prove by induction that for the Fibonacci numbers $F(n)$ with $n \ge 6$, $F(n) \ge 2^{n/2}$

Prove by induction that $F(n) \ge 2^{n/2}$ for $n \ge 6$ I've done the following steps: 1) Base case: $F(6) = 8$, $2^{0.5 \cdot 6} = 8$, base case proved. 2) Induction: let's assume that $F(k) ...
6
votes
3answers
411 views

Some trouble with the induction

Prove, that for any positive integer $n \geqslant 2$ we have the inequality $$ \frac{ 4^n }{ n+1 } < \frac{ (2n)! }{ (n!)^2 }.$$ For $n=2$ the inequality is true. Directly just take and ...
-6
votes
0answers
33 views

Prove by induction this notation [on hold]

Prove by induction? For $n\geq0$, $$\sum_{i = 0}^n (n i+2)^2={1 \over 3}(n+1)(2n+1)(2n+3)$$ Please help me.
1
vote
0answers
32 views

Verification of Basic Proof in Spivak Calculus (Induction)

I have began working through Spivak's Calculus book and trying to do the problems at the end of the chapters. I am rather new to proof, so forgive the naivety of this type of question. I am wanting ...
1
vote
0answers
7 views

Binary addition preserving Hamming weights

Let $x,y$ be two $n$-bit strings, with Hamming weights (number of $1$ bits) equal to $w_{1},w_{2}$, respectively. Let $z$ be the binary representation of the sum $x+y$, where we interpret $x$ and $y$ ...
1
vote
1answer
18 views

Confusion regarding differences between strong induction and simple induction

I don't know how to prove that any proof by induction is also proof by strong induction nor any proof by strong induction can be converted into a proof by simple induction? An example would be useful ...
6
votes
2answers
48 views

Convergence and divergence depending on whether $n$ is odd or even

It is part of one problem I am working on: I want to prove the following conjecture ($x\ne q\pi$ where $q\in\Bbb Q$) $$\sum_{n=1}^{\infty}\frac{\sin^{2k-1}(nx)}{n^{\alpha}}\quad\text{converges ...
6
votes
2answers
72 views

Proving that $x^m+x^{-m}$ is a polynomial in $x+x^{-1}$ of degree $m$.

I need to prove, that $x^m+x^{-m}$ is a polynomial in $x+x^{-1}$ of degree $m$. Prove that $$x^m+x^{-m}=P_m (x+x^{-1} )=a_m (x+x^{-1} )^m+a_{m-1} (x+x^{-1} )^{m-1}+...+a_1 (x+x^{-1} )+a_0$$ on ...
-1
votes
0answers
46 views

Induktion with a k term

Hi again i am having trouble with another induction number that is $\sum_1^n$ 1/1+2...+k = 2n/n+1 For n = n+1 I have LHS: 2/(k(k+1) * 2n/(n+1) which i have expanded to 2/(n+1)(n+1)+1* ...
0
votes
3answers
40 views

Question regarding an induction proof

I am stuck on a question regarding induction. I know that we are supposed to solve it using 3 steps: the base step, the n= p step and n = p+1. The question is prove that ...
-1
votes
3answers
31 views

Induction well ordering principle [duplicate]

Can someone help me with the following question. I have mangaged to solve this question using well ordering prinicple but cant proof it by the induction method. I cant proof that n+1 holds in the ...
0
votes
0answers
33 views

Proof that all derivatives at zero equal zero [duplicate]

Trying to prove that given $$ f(x)=\begin{cases} e^{-{\frac {1}{x^2}}} & \text{if $x\ne0$}\\[6px] 0 & \text{if $x=0$} \end{cases} $$ that $\ f^{(n)}_{(0)}=0$ for every n$\ \in\mathbb N$ ...
0
votes
1answer
83 views

Prove that a tree in which every vertex has degree at most 2 is a simple path

Prove that a tree in which every vertex has degree at most 2 is a simple path. More precisely: Let $G = (V,E)$ be an undirected tree, with $|V| = n \geq 1$ and assume that every vertex has degree ...
0
votes
2answers
70 views

Prove by induction $\sum\limits_{k=m}^{\ n}{n\choose k}{k\choose m}={n\choose m}2^{n-m}$

I can't figure out what is the base case. Could someone show the steps?
3
votes
3answers
105 views

Identity on Fibonacci numbers: $F_{2n}^2=F_{2n+2}F_{2n-2}+1$?

Let $F_n$ be the Fibonacci Sequence ($F_1=F_2=1, F_{n+2}=F_{n+1}+F_{n}$). Prove that $F_{2n}^2=F_{2n+2}F_{2n-2}+1$. I've tried everything from induction to telescoping series but I haven't got close. ...
0
votes
1answer
37 views

Strong Induction: Prove that sqrt(2) is irrational

This question comes directly out of Rosen's Discrete Mathematics and It's Applications pertaining to Strong Induction. Use strong induction to prove that $\sqrt{2}$ is irrational. [Hint: Let $P(n)$ ...
0
votes
2answers
64 views

How to find whether this series converges or diverges?

Let's suppose I have been given a series that looks like this: $$\sum_{n=1}^n\frac{1\cdot 3\cdot 5\cdot\cdots\cdot(2n-1)}{2\cdot5\cdot8\cdot\cdots\cdot(3n-1)}$$ What I have been thinking of doing ...
3
votes
1answer
113 views

Finalising proof from Humphreys´ “Introduction to Lie Algebras and Representation Theyory”

$L=\mathfrak{sl}(2, \mathbb{F})$ with standard Chevalley basis $(x, \ y, \ h)$ and $a, \ c\in \mathbb{Z}^{+}$. Humphrey gives a Lemma in chapter 26.2 saying: ...
4
votes
5answers
67 views

$p$ divides $n^p-n$

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for ...
0
votes
1answer
19 views

Verifying quadratic reciprocity for the Jacobi symbol

I am trying to prove: If $m,n$ are odd coprime positive integers, then $$\Big(\frac mn\Big)\Big(\frac nm\Big)=(-1)^{\large\frac{m-1}2\frac{n-1}2},$$ where $\big(\frac mn\big)$ is the Jacobi ...
2
votes
2answers
34 views

Proving binary integers

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with binary integers (For ${0, 1, 2, 3}$ we have the representations $0, 1, 10, ...
1
vote
3answers
81 views

Induction Proof: $\sum_{k=1}^n k^2$

Prove by induction, the following: $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}6$$ So this is what I have so far: We will prove the base case for $n=1$: $$\sum_{k=1}^1 1^2 = \frac{1(1+1)(2(1)+1)}6$$ We ...
0
votes
2answers
74 views

Explain how the proof is done

A solution of matrix problem appears to be as follows some one explain the following in the solution why is A cube is eliminated and fourth power of A is obtained? In the seventh line In the ...
0
votes
2answers
40 views

Proving if $-1 < x < 1$ then $x^1 + x^2 + \cdots + x^n = \frac{x-x^{n+1}}{1 - x}$

Let $$S_n = x + x^2 + x^3 + \cdots + x^n$$ then $$xs_n = x^2 + x^3 + \cdots + x^n + x^{n+1}$$ This is taken from book "An concise introduction to pure mathematics" : Why does inserting $x$ to ...
0
votes
3answers
75 views

Proving “The sum of n consecutive cubes is equal to the square of the sum of the first n numbers.”

From http://www.themathpage.com/aPreCalc/mathematical-induction.htm states : should : not be : $$1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^3+(n + 1)^3}{2^3}$$ as everthing to left of equation is ...
2
votes
2answers
42 views

Solution to Fibonacci Recursion Equations

Let the sequence $(a_n)_{n\geq0}$ of the fibonacci numbers: $a_0 = a_1 = 1, a_{n+2} = a_{n+1} + a_n, n \geq 0$ Show that: i) $$a^2_n - a_{n+1}a_{n-1} = (-1)^n \text{ for }n\geq1$$ I try to show ...
3
votes
1answer
39 views

Induction Proof: $2$ divides $n^2 + n$ for each $n \in \mathbb{N}$

So I am looking at some induction questions and I am trying to solve them on my own but I am getting stumped and frustrated. There was a previous question question that was answered, but I changed it ...
0
votes
1answer
70 views

Prove that a $k$-degenerate graph is ($k+1$)-colorable

A graph is $k$-degenerate if every induced subgraph contains a vertex of degree at most $k$. How can I prove that a $k$-degenerate graph is ($k+1$)-colorable?
1
vote
4answers
34 views

Proving recurrence by mathematical induction

$f(1)=1,$ $f(n)=2f(n-1)+3$ ($\forall n>1$) has the following closed form solution $f(n)=2^{(n+1)}-3$ I understand that I can simply show that the recurrence is equal to $2^{(n+1)}-3$,but not ...
2
votes
2answers
43 views

Proof by contradiction and mathematical induction

$\sum_{i=1}^n {2\over3^i}={2\over3}+{2\over9}+\dots+{2\over3^n}=1-{({1\over3})^n}$ I had this problem in class and we proved using 2 different methods: contradiction and mathematical induction. I ...
0
votes
0answers
28 views

Mathematical induction, sum [duplicate]

Problem: Prove the following by using the Principle of Mathematical Induction: $$1+2+2^2+...+2^{(n-1)}=2^n-1$$ I can prove it for $n=1,$ but I cannot understand what to do next. I would be truly ...
1
vote
3answers
66 views

Prove by induction: $\sum\limits_{i=1}^{n}(4i+1) = 2n^2 + 3n$

Prove by induction: $$\sum\limits_{i=1}^{n}(4i+1) = 2n^2 + 3n$$ It's just the numbers that confuse me; I know how to do a simple induction proof that first for $p(k)$ and then for $k+1$ etc but ...
0
votes
2answers
37 views

Prove by math induction

$\forall n \geq 2$ $\frac{7}{9} \times \frac{26}{28} \times \ldots \times \frac{n^3 -1}{n^3 + 1} = \frac{2}{3} \times (1 + \frac{1}{n(n+1)})$ After basis step i went this far: $ ...
1
vote
0answers
23 views

Induction Proof from Thomas Judson book on abstract algebra

I'm trying to prove $$^n\sqrt{a_1\times a_2\times...\times a_n}\leq \frac{1}{n}\sum_{k=1}^na_k, \quad a_i\in \mathbb{Z}^+$$ by Induction. The case is true for $n=1$ so I assumed true for $n=k$. I then ...
2
votes
1answer
67 views

Quantifier-free induction and comparison with $\sqrt{2}$

I am trying to understand quantifier-free induction in the system called PRA - primitive recursive arithmetic which states the following: $$ \frac{ \varphi[0] \quad \varphi[n] \implies ...
0
votes
4answers
62 views

Prove by induction that sum of an odd number of odd numbers is odd

Prove by induction that if $n$ is odd and $a_1,\,\cdots,\,a_n$ are odd, then $\begin{aligned}\sum_{i = 1}^n a_i\end{aligned}$ is odd. Progress: If $n = 1$ then $\sum_{i = 1}^1 a_i = a_1$, so the ...
-1
votes
0answers
23 views

mathematical induction, addition squares [duplicate]

I am trying to solve following problem: 1^2 + 2^2 + 3^2 + ... + n^2=(n(n+1)(2n+1))/6 please write complete solution in detail. I viewed some solutions but I am lost. Thank you very much in advance. ...
0
votes
1answer
42 views

Prove by induction $(\frac{n}{e})^n<n!<e(\frac{n}{2})^n,n\in \mathbb{N}$

$n!>(\frac{n}{e})^n$ $$(n+1)!=n!(n+1)>(\frac{n}{e})^n(n+1)=(\frac{n+1}{e})^{n+1}\times \frac{(\frac{n}{e})^n(n+1)}{(\frac{n+1}{e})^{n+1}}>(\frac{n+1}{e})^{n+1}$$ This implies, but I think ...
0
votes
0answers
9 views

Problem with understanding the induction when proving Sauer Lemma.

I will replicate the proof here which is from the book "Learning from Data" B(N, k) is the maximum number of dichotomies on N points such that no subset of size k of the N points can be shattered by ...
1
vote
5answers
129 views

Show that $30 \mid (n^9 - n)$

I am trying to show that $30 \mid (n^9 - n)$. I thought about using induction but I'm stuck at the induction step. Base Case: $n = 1 \implies 1^ 9 - 1 = 0$ and $30 \mid 0$. Induction Step: Assuming ...
1
vote
2answers
70 views

Version of the Axiom of Induction for Real Induction?

Mathematical induction can be done using the axiom of induction, which is given as a formula written in the language of mathematical logic. Is there a way to express the ideas behind 'real induction' ...
2
votes
9answers
131 views

Proof by induction that $3^n - 1$ is an even number

How to demonstrate that $3^n - 1$ is an even number using the principle of induction? I tried taking that $3^k - 1$ is an even number and as a thesis I must demonstrate that $3^{k+1} - 1$ is an even ...
0
votes
1answer
65 views

prove that $A(n) : \left(\frac n3\right)^n\lt n!\lt \left(\frac{n}{2}\right)^n$ for all $n\ge 6$

prove that $A(n) : \left(\frac n3\right)^n\lt n!\lt \left(\frac{n}{2}\right)^n$ for all $n\ge 6$ first check $n=6$ : $2^6<6!<3^6$ ok then $n\gt 6$ assume $A(m)$ is true, then show ...
0
votes
2answers
81 views

Prove by induction that $\sum_{i=1}^{n} 2i=(n+1)n$, for every positive integer n. [duplicate]

Can anyone explain the concept behind this? I just don't get how I should proceed with it? Like each step, why and how is it done? Prove by induction that $\displaystyle\sum_{i=1}^{n} 2i=(n+1)n$, ...
0
votes
2answers
53 views

Simplifying the product $\prod\limits_{k=1}^n \left(1-\frac1{k^2}\right)$ [duplicate]

Can we simplify the given product to a general law? $$\left(1-\frac{1}{4}\right)\left(1-\frac{1}{9}\right)\left(1-\frac{1}{16}\right)...\left(1-\frac{1}{n^2}\right)$$
2
votes
1answer
89 views

Induction involving lines and regions

If n $\geq$ 2 lines are drawn in the plane, they divide it into a number of regions. Assume that no two lines are parallel and that no three lines meet at a single point. Show that it is possible to ...