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
0answers
19 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
61 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
28 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
68 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
40 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
171 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 ...
2
votes
3answers
81 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
26 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?
2
votes
2answers
67 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
63 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} ...
0
votes
0answers
25 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
37 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
64 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
44 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 ...
2
votes
1answer
63 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
16 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
85 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
83 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
273 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
71 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
419 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
5answers
72 views

Prove that $|A|=n\implies\left|\mathcal P(A)\right|=2^n$ [closed]

Prove by induction: For all integers greater than or equal to $0$, if a set $A$ has $n$ elements, then $\mathcal{P}(A)$ has $2^n$ elements. I'm not sure of the best way to approach this problem. Any ...
1
vote
1answer
51 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}$, ...
1
vote
0answers
79 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 ...
2
votes
7answers
83 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 ...
0
votes
1answer
24 views

Prove $x^n$ + x < ($x^n$)x using PMI

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) ...
0
votes
2answers
72 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. ...
1
vote
0answers
32 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
50 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
15 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 ...
2
votes
1answer
72 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 ...
3
votes
0answers
35 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 &= ...
0
votes
1answer
12 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 ...
29
votes
4answers
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
58 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
63 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
97 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
33 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 ...
7
votes
7answers
135 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
36 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
39 views

Explaining setup of the inductive step in a Fibonacci proof exercise

I have the following exercise to be proved by mathematical induction and also I have the answer about how to solve it: $$ f(0) - f(1) + f(2) - \ldots - f(2n-1) + f(2n) = f(2n-1) - 1 $$ where ...
1
vote
1answer
32 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: $$ ...
2
votes
3answers
55 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
49 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
29 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 ) ~=~ ...
1
vote
2answers
19 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
40 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 ...
38
votes
9answers
1k 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
38 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 ...