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

0
votes
2answers
133 views

Using induction to prove a sequence is always less than a given number

Let $f(1)=2$ and $f(n+1)=\sqrt{3+f(n)}$. Prove that $f(n)<2.4$ for all $n\ge 1$. I established a base case when $n=1$ and then moved on to the inductive step by assuming the statement is true for ...
1
vote
0answers
21 views

Recurence with multiple variables and functions

Is there an easy way to solve a recurrence given with two variables and three different functions? Actually I'm looking for the solution of: $$A(n,k)=A(n-2,k-1)+A(n-3,k-1)+R(n-2,k-1)+L(n-2,k-1) $$ $$...
0
votes
3answers
84 views

Fibonacci induction proof?

The Fibonacci Numbers $(f_n)$ are defined $f_1=f_2=1$, and $f_n=f_{n-1}+f_{n-2} ,\,\,\,\forall n \geq2$. Prove that for every integer $n \geq 1$, $$f_1 +f_2 +···+f_n =f_{n+2}−1$$
0
votes
1answer
170 views

Induction solution for game of coins

Consider a game in which, initially, there is a pile of n coins placed on a table. There are two players who alternate turns. Each player, on her or his turn, removes either one, two, or three coins ...
1
vote
3answers
72 views

Proving $2^n\leq 2^{n+1}-2^{n-1}-1$ for all $n\geq 1$ by induction

I am trying to prove that for every element of $\mathbb{N}$, that $2^n \leq 2^{n+1} - 2^{n-1} - 1.$ I started by showing that initial case, of $n=1$, is true. Then I proceed to the ...
0
votes
2answers
46 views

How to proof $f_{n+1}(x) = x f_n(x) - f_{n-1} (x),\quad n \geqslant 1$ by induction?

Let $$ f_n (x) = \det \begin{bmatrix} x & 1 & 0 & \cdots & 0 \\ 1 & x & 1 & 0 & 0 \\ 0 & 1 & x & 1 & \vdots \\ \vdots & & & \ddots & 1 ...
0
votes
1answer
24 views

How to use Induction properly?

I would like to prove the following equation using induction. However that seems somehow impossible at least for me: $\sum\limits_{k=1}^{2n} {(-1)^k \cdot k^2}=(2n+1)\cdot n$ I tried to show that ...
2
votes
3answers
191 views

How to prove through induction

How can I prove by induction that $$\binom{2n}n<4^n\;?$$ I have solved for the base case, $n=1$, and have formulated the induction hypothesis. I was thinking about Pascal's identity for the rest,...
3
votes
3answers
107 views

Showing $1+2+\cdots+n=\frac{n(n+1)}{2}$ by induction (stuck on inductive step)

This is from this website: Use mathematical induction to prove that $$1 + 2 + 3 +\cdots+ n = \frac{n (n + 1)}{2}$$ for all positive integers $n$. Solution to Problem 1: Let the ...
0
votes
3answers
27 views

question on prove by induction that for each n$\in\mathbb{N}_{\ge2}$, $n^2$< $n^3$

I have to prove by induction that for each n$\in\mathbb{N}_{\ge2}$, $n^2$< $n^3$. If I try to prove for P(1) I end up with 1 < 1. Is this right? Why does it or does it not make sense?
3
votes
2answers
183 views

Is there a much simpler proof for Euler factorial formula?

Euler formula for factorial stated as follows Theorem [Euler]: For any non negative integers $a$ and $n$ such that $a\geq n$ $$ n!=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(a-k)^n$$ Proving this ...
4
votes
1answer
83 views

Dynamical system $x_{n+1} = \frac{1}{2}(x_n - \frac{1}{x_n}) \ \ , \ \ n = 0, 1 , 2,…$

Consider the dynamical system $$ x_{n+1} = \frac{1}{2}(x_n - \frac{1}{x_n}) \ \ , \ \ n = 0, 1 , 2,... $$ So by using the substitution $x_n = \cot(y_n)$, I have found: $$ x_n = \cot(\cot^{-1} (x_0)...
0
votes
0answers
27 views

Help on Proof By Induction

We had to prove the following algorithm by induction: $ a^n = a^{n/2*2} = a^{n/2}*a^{n/2} $ if $n$ is even $ a^n = a^{\frac {n-1}2*2}*a = a^{\frac {n-1}2} * a^{\frac {n-1}2} * a $ if $n$ is ...
1
vote
1answer
92 views

Huffman Encoding Symbol Probability [duplicate]

Prove for two symbols a and b, if p(a) >= p(b), then according to Huffman encoding algorithm, the resultant code length L(a) <= L(b). I did several examples of this and it is true. But how can I ...
1
vote
2answers
265 views

Huffman Encoding Proof Probability and Length

If the frequency of symbol i is strictly larger than the frequency of symbol j, then the length of the codeword for symbol i is less than or equal to the length of the codeword for symbol j. I ...
1
vote
2answers
73 views

Prove by induction on $n$ that when $x \gt 0$, $ (1+x)^n \ge 1+nx+\frac{n(n-1)}{2}x^2 \text{ for all positive integers } n. $

Here's the problem: Prove by induction on $n$ that when $x \gt 0$ $$ (1+x)^n \ge 1+nx+\frac{n(n-1)}{2}x^2 \text{ for all positive integers } n. $$ So, clearly the base case is true. Here's how far ...
4
votes
1answer
142 views

Principle of mathematical induction

In his book “Introduction to Mathematical Philosophy” Bertrand Russell seems to reach the conclusion that mathematical induction is a definition and not a principle. In essence he states that ...
0
votes
1answer
36 views

find coefficients of a polynomial given k roots

Lets say that I have k roots for a polynomial and I am trying to find the coefficients of the terms in the polynomial. (x - r1)(x - r2)(x - r3) ... (x - rk) ...
2
votes
4answers
126 views

proving that for every integer $x$, if $x$ is odd, then $x + 1$ is even (induction)

So I have to write a proof that "for every integer $x$, if $x$ is odd, then $x + 1$ is even". I understand what I have to do but I always get stuck at the last step which is prove that it's true for $...
4
votes
5answers
403 views

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$.

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$. I've started by letting $P(n) = n^3+11n$ $P(1)=12$ (divisible by 6, so $P(1)$ is true.) Assume $P(k)=k^3+11k$ ...
5
votes
6answers
305 views

Proof by Induction Problem

I need to prove that for natural numbers $a$, and positive integers $n$, the number $a^{2n+1}-a$ is divisible by $6$. I have proved the case when $n=1$, that $a^3-a$ is divisible by $6$. I'm having ...
1
vote
2answers
87 views

Partial Sum of this function

What are the steps to finding the partial sum formula? $$\sum\limits_{k=1}^\infty\frac{k}{2^k}=2$$ The professors asked us to search for its partial sum and then prove it by induction
3
votes
5answers
551 views

Fibonacci sequence and the Principle of Mathematical Induction

Consider the Fibonacci sequence, $F_n$. Prove that $2 ~\vert~ F_n$ if and only if $3 ~\vert~ n$, using the principle of mathematical induction. I know that I have to prove two implications here. ...
1
vote
1answer
176 views

Proof by Induction: Squared Fibonacci Sequence

I've been working on a proof by induction concerning the Fibonacci sequence and I'm stumped at how to do this. Theorem: Given the Fibonacci sequence, $f_n$, then $f_{n+2}^2-f_{n+1}^2=f_nf_{n+3}$, $∀n∈...
1
vote
0answers
150 views

How to prove $\sum_{k=0}^n \binom{n}{k}=2^n$ and $\sum_{i=1}^n i(n-i+1)= \binom{n+2}{3}$ by induction? [closed]

Prove by induction that: $\sum_{k=0}^n \displaystyle\binom{n}{k}=2^n$. Hint: When you consider this equality for $n-1$, add it to itself and use a famous property of the binomial coefficients ...
2
votes
7answers
107 views

How do you prove that $4^n > n^3$ for all positive integers $n$?

Prove that $4^n > n^3$ for every positive integer $n$ using the Principle of Mathematical Induction. I am well aware of how to use this proof technique. I first showed that P(1) is true: $4^1 >...
1
vote
1answer
77 views

Prove $x^n + x < (x^n)x$ using induction.

I need to prove $x^n$ + x < $x^n\cdot$ x, n $\in$ N, x $\in$ R>2 using induction. I started by $x^n$ + x + (x^(n+1)+x) < ($x^n\cdot$ x) + (x^(n+1)+x) I simplified to this: < 2x^(n+1) ...
1
vote
2answers
91 views

INMO Problem with even function proof. [duplicate]

Let $n$ be a natural number. Show that $$\left[ \frac{n}{1} \right ] + \left[ \frac{n}{2} \right ] + \left[ \frac{n}{3} \right ] + \cdots + \left[ \frac{n}{n} \right ] + [\sqrt{n}]$$ is even. Here $[...
2
votes
0answers
50 views

Exercise in induction (including double indices)

The following is for an exam preparation exercise in induction Problem: Let $f(x)=|x| = \sqrt{x_1^2 + x_2^2 + \dots + x_n^2}$ and $g(x)=|x|^{2k+1}$. Let $N \leq n$ and let $k \in \mathbb{Z}$, ...
2
votes
1answer
56 views

What proof is there that all numbers behave as the numbers we commonly use?

This is a question from someone who is very new to math, so please excuse my ignorance. In a couple of places, I have learned proof by induction, which claims to prove for a set of all integers. A ...
0
votes
0answers
18 views

Monotonicity of n-th root by induction

Suppose a,b are real numbers. I'm trying to prove that $\forall n\geq 1$ ( $0<a<b$ entails $0 <a^{1/n}<b^{1/n}$ ) with the method of Induction. P.S : I already know how to ...
1
vote
1answer
78 views

Fifth root of an even number

Assume $x>1$ is an even integer, show that. $$\sqrt[5]{x} \notin \mathbb{N}$$ I am not sure if this is actually a true theorem, I am conjecturing based on $2, 4, 6, 8, 10, .... 126$. I am ...
4
votes
0answers
53 views

Induction proof - not sure how to proceed with next step

Define two sequences $A_n, B_n$ as follows: \begin{align*} A_1 &= 1\\ A_2 &= 3\\ A_3 &= 2 \cdot 3+1=7 \\ A_4 &= 2 \cdot 7 + 3 = 17\\ A_5 &= 2 \cdot 17 + 7 = 41\\ A_n &= 2A_{n-...
0
votes
1answer
57 views

finite intersection of a family of sets same as countable intersection?

I am reading definition of semi-algebra and one of its properties is that it is closed under finite intersection. In that case can't it be proved that it is also closed under countably infinite ...
34
votes
3answers
2k views

Avoiding proof by induction

Proofs that proceed by induction are almost always unsatisfying to me. They do not seem to deepen understanding, I would describe something that is true by induction as being "true by a technicality". ...
3
votes
3answers
108 views

For all integers $n \ge 1$, prove 6 divides $n(n+1)(n+2)$ by PMI.

For all integers $n \ge 1$, prove 6 divides $n(n+1)(n+2)$ by PMI. I check for my base case, it holds. Then, my inductive hypothesis that for any arbitrary $n \ge 1$, 6 divides $n(n+1)(n+2)$ so ...
0
votes
1answer
225 views

Induction step of a power of 2 with ceiling function

I have to prove the following excercise: "Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integersto the set of ...
0
votes
1answer
135 views

Proving some property of a Formal Logic Language [duplicate]

I am stuck at this problem: Let $\Sigma = \{\lnot,\lor,\land,\rightarrow,\leftrightarrow,(,),P_1,...,P_n\}$ be an alphabet. Now let's define the set of logical expressions $\mathscr{L} \subseteq \...
1
vote
1answer
53 views

How can I fix this proof using transfinite induction of the existence of bases of normed vector spaces?

I want to prove that every normed vector space has a basis. The following proof relies on the principle of transfinite induction. I believe that it is flawed because I'm not so sure if it's possible ...
10
votes
8answers
544 views

Proving $\sum_{k=1}^n k k!=(n+1)!-1$

Prove: $\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$ (preferably combinatorially) It's pretty easy to think of a story for the RHS: arrange $n+1$ people in a row and remove the the option of everyone ...
1
vote
5answers
84 views

Proving $n! < n^n$ by induction for all $n\geq 2$.

I am having trouble simplifying an induction question. The question is: Let $P(n)$ be the statement that $n! < n^n$ where $n$ is an integer greater than $1$. My work so far: Base case $n = 2$ $...
1
vote
1answer
34 views

Show by induction: $ \frac{a_{2n+4}}{a_{n+2}}=\frac{a_{2n+2}}{a_{n+1}}+\frac{a_{2n}}{a_{n}}$

I would appreciate if somebody could help me with the following problem: Q: Sequence $\{a_n\}$; satisfy $a_{n+2}=a_{n+1}+a_{n}, a_1=1,a_2=1$ Show by induction: $$ \frac{a_{2n+4}}{a_{n+2}}=\frac{a_{...
2
votes
3answers
76 views

Show $P(1), P(2),…,P(99)$ true statements but $P(100)$ is false.

Provide a sequence of statements, $P(n),$ for $n\in \mathbb{N}$ such that $P(1), P(2),...,P(99)$ are all true but $P(100)$ is a false statement. My try: Let $n\in \mathbb{N}$ and let $0\notin \...
2
votes
1answer
74 views

Prove or disprove $n \geq 2 ~\rightarrow~ \prod \limits_{i=1}^{n} \left ( 1 - \frac{1}{i^2} \right ) ~=~ \frac{n+1}{2n}$

I am working on one of my HW assignments $$ \forall n \in \mathbb{Z}, ~ n \geq 2 ~\rightarrow~ \prod \limits_{i=1}^{n} \left ( 1 - \frac{1}{i^2} \right ) ~=~ \frac{n+1}{2n} $$ And i am not ...
0
votes
1answer
35 views

prove or disprove $n > 0 ~\rightarrow~\prod \limits_{i=1}^{n} \left ( \frac{1}{2i~+~1} \cdot \frac{1}{2i~+~2} \right ) ~=~ \frac{1}{(2n~+~2)!}$

I am working on one of my HW assignments $$ \forall n \in \mathbb{Z}, ~ n > 0 ~\rightarrow~ \prod \limits_{i=1}^{n} \left ( \frac{1}{2i~+~1} \cdot \frac{1}{2i~+~2} \right ) ~=~ \frac{1}{(2n~...
2
votes
2answers
29 views

Suppose a matrix A is nxn, and that v1,v2 are in R^n…

Sorry, this is my first time posting here, so if my question is worded incorrectly, please let me know. Anyway, I'm studying for an exam coming up, and this is one of the questions that I'm trying to ...
0
votes
2answers
64 views

mathematical induction to establish inequality

Studying for a test in discrete mathematics and I cannot seem to grasp the explanations in the textbook regarding these questions. Using mathematical induction, prove that $$2^n > n^2, \text{for ...
53
votes
10answers
2k views

Fake induction proofs

Question: Can you provide an example of a claim where the base case holds but there is a subtle flaw in the inductive step that leads to a fake proof of a clearly erroneous result? [Note: Please do ...
2
votes
1answer
44 views

Help with how to prepare the inductive step of a strong induction exercise.

I have the following exercise: "Use strong induction to prove that $f_1^2 + f_2^2 + \cdots + f_n^2 = (f_n)(f_{n+1})$ where $f_n$ in the nth Fibonacci number." This is what I have done: Fibonacci ...
1
vote
4answers
136 views

I'm having trouble with induction. Prove $1 + 2^3 + 3^3 + … + n^3 = \frac{((n^2)(n+1)^2)}4$ [duplicate]

I started a new course and I'm expected to know this stuff, and I'm having trouble learning some on my own. I'm stuck with this problem: Prove $1 + 2^3 + 3^3 + ... + n^3 = \frac{((n^2)(n+1)^2)}4$ ...