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
1answer
166 views

prove by induction that $\sum_{k=0}^n {n \choose k} = 2^n$ [duplicate]

I have proved previously that $\sum_{k=0}^n {n \choose k} = 2^n$ by using the binomial theorem. I was wondering, however if it were possible to solve this using a proof of induction.
0
votes
1answer
36 views

$P(0), P(1)$ hold and $P(n) → P(n + 2)$ for $n\geq 1$. For which $n$ is $P(n)$ T?

The question is: $P(0)$ hold $P(1)$ hold $P(n) \rightarrow P(n + 2)$ for $n \geq 1$ For which values of $n$ does $P(n)$ hold? My initial answer was that $P(n)$ holds for all odd positive ...
0
votes
3answers
78 views

Does $ \sum_{k=0}^n k {n \choose k}$ have a convenient exponential equivalent? [duplicate]

I know that: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ Does $$0 {n \choose 0} + 1 {n \choose 1} + ... + n {n \choose n} = ??$$ have some convenient simplification?
1
vote
2answers
33 views

Proof by induction: $(1+\alpha)^n\ge 1+n\alpha > +\frac{n(n-1)}{2}\alpha ^2$

so I have this problem. It asks me to prove an expression by induction. Let $n$ be a positive integer, and $\alpha$ any nonnegative real number. Prove by induction that$$(1+\alpha)^n\ge ...
2
votes
3answers
73 views

Prove $\frac{(2n)!}{2^nn!}$ is always an integer by induction.

Hey guys so I have this math question. I have to prove that $\frac{(2n)!}{2^nn!}$ is always an integer by induction where $n$ is a positive integer. This is my approach. First I check the initial case ...
0
votes
1answer
135 views

Proving strong induction implies weak induction

I have been given the following (non-predicate form) definitions for the Principle of Mathematical Induction (weak and strong,respectively) as follows: $I$: Let $U\subseteq\mathbb{N}$ with $1\in U$ ...
1
vote
1answer
41 views

Induction with floor limits

I ran into an exercise in a book that asked the following: Prove that $$S(n) = \sum_{\ell=0}^{[n/2]}\binom{n}{2\ell}p^{2\ell}(1-p)^{n-2\ell} = \frac{1+(1-2p)^n}{2},$$ where $[x] =$ the floor ...
1
vote
1answer
151 views

Palindrome Induction Proof

Consider strings made up only of the characters $0$ and $1$; these are binary strings. A binary palindrome is a palindrome that is also a binary string. (a)Let $f(n)$ be the number of binary ...
2
votes
3answers
97 views

Fibonacci Loop Invariants

I've taking an Algorithms course. This is non-graded homework. The concept of loop invariants are new to me and it's taking some time to sink in. This was my first attempt at a proof of correctness ...
4
votes
2answers
32 views

Induction question

I have to prove that $$P(n):\quad 1^2-2^2+3^2-\dots+(-1)^{n+1}n^2=(-1)^{n+1}T_n$$ where $T_n=1+2+\ldots+n=\frac{n(n+1)}{2}$. I know I have to solve by induction. So, I showed a base case that when ...
0
votes
0answers
38 views

Proof of Pigeonhole Principle using equipotence and induction

I am attempting to prove the form of the Pigeonhole Principle which states "$\forall n,m \in \mathbb{N}$, the set $\{1,\cdots,n+m\}$ is not equipotent to the set $\{1,\cdots n\} $". Here is my proof ...
1
vote
1answer
36 views

Fibonacci sequence developing [duplicate]

For the sum $$\sum_i^n {n-i \choose i}$$ I evaluate it for $n=1,2,3,4,5$ For $n=1$ we have $$\sum_{i=0}^1 {1-i \choose i} = {1 \choose 0} + {0 \choose 1} = 1 + 0 = 1$$ For $n=2$ we have ...
0
votes
1answer
54 views

Prove by Induction AM-GM

Suppose that $a,b \in \mathbb{R}$ are positive. Prove that: $$\sqrt{ab} \leq \frac{a + b}{2}$$ Note: This inequality is known as the inequality between arithmetic mean, $\frac{a + b}{2}$, and ...
2
votes
1answer
78 views

Even-order derivative of $y = x\sin (x)$

How do I find the general formula for the even-order derivative of $y = x\sin (x)$? I tried using integration by parts and separation followed by mathematical induction, but I failed to obtain the ...
0
votes
1answer
72 views

Prove by induction that if the first car stops, all of them stop [duplicate]

I have to prove this by induction: $n$ cars are travelling down a narrow one-way street. We know that: The distance d between each two cars is the same. The safe breaking distance b is ...
0
votes
0answers
72 views

Inequality of arithmetic and geometric means by induction

if $a_1,a_2,a_3,\ldots,a_n≥0$ then the arithmetic mean is: $A_n=\frac{a_1+a_2+a_3+\cdots+a_n}{n}$ and the geometric mean is: $G_n=\sqrt[n]{a_1a_2a_3\ldots a_n}$ (a) Making use of the fact that ...
0
votes
4answers
47 views

Should be simple proof by induction

I am trying to prove $n^2>2n+1$ for $k\ge 4$. Intuitively this is true since $\lim\limits_{n\rightarrow\infty}(2+1/n)=2$. Obviously $16>9$. Assume $k^2>2k+1 \implies k^2+2k+2>2k+1+2k+2 ...
2
votes
3answers
46 views

Proving inequality by induction only

Suppose $a_1,\dots,a_n$ are real positive numbers s.t. $\prod_{i=1}^n a_i=1$. My book claims that by induction only (i.e. the use of AM-GM is forbidden), one can prove that $$\sum a_i\ge n$$ and that ...
2
votes
2answers
66 views

Proving $n! \ge 2^{n-1 }$for all $n\ge1 $by mathematical Induction

Im trying to solve the following question In the second step where do they get $k!=2^k-1?$
2
votes
1answer
57 views

How to use well-ordering to form a “least counterexample derived contradiction” to prove rule for obtaining the remainder when dividing $3^n$ by 13?

By the division with remainder theorem, we know that there exists $q \in \mathbb{Z}$ and $r \in \mathbb{Z}$, where $0 \leq r < 13$, such that: \begin{equation*} ...
1
vote
4answers
77 views

How to prove an identity containing binomial coefficients

I am trying to prove the identity $$\sum_{k=1}^n (3^k - 1) \binom{n}{k} = 4^n - 2^n$$ where $\binom{n}{k}$ is the binomial coefficient n over k or n choose k.
1
vote
5answers
63 views

Proof about specific sum of Fibonacci numbers

Let $F_k$ denote the $k$-th Fibonacci number. Find a formula for and prove by induction that your formula is correct for all $n > 0$. $$ (-1)^0 F_0+(-1)^1 F_1+(-1)^2 F_2+\cdots+(-1)^n F_n=\ ? $$ I ...
0
votes
1answer
40 views

Proof by induction that *p* = 1/*p*-1 in golden rectangle exercise

The initial rectangle's dimensions is L0 for the length and l0 for the width. A golden rectangle can be obtained when it has the same proportions as the initial rectangle, so p = L0/l0 I am first ...
1
vote
2answers
37 views

induction of sequence

I am really stuck on one of my excersies. I know it's true for n=1, but I can figure out how to prove it for k+1. This excersise it considerably more difficult than the one we discusses in class. I ...
0
votes
0answers
9 views

Proof By induction on inequality [duplicate]

I'm trying to answer this question: Let $x > −1$. Prove by induction that $(1 + x)^n \ge ≥ 1 + nx$ for all $n ∈ ℕ$ All I have been able to prove up until now is that the base cases hold. ...
1
vote
1answer
31 views

proof by induction in worded example

I'm trying to answer the following question: The boxes Banana Ltd. uses to ship bananas come in two sizes, one that holds three bananas and one that holds five bananas. The company promises to ...
5
votes
2answers
909 views

Flaw in this proof by induction

I'm trying to find a flaw in the following proof, but I am unsure if I am correct or not: Identify the flaw in the proof that $2n = 0$ for all $n \ge 0$. Base case: If $n=0$ then $2\cdot n = 2\cdot ...
2
votes
4answers
71 views

How can the proof by induction be reliable when it depends on the number of steps?

Yesterday, I got a math problem as follows. Determine with proof whether $\tan 1^\circ$ is an irrational or a rational number? My solution (method A) I solved it with the following ways. I ...
-1
votes
1answer
63 views

Find the smallest $N \in Z^+$ satisfying the property that $n^2 \leq 2^n$ for all $n \geq N$, and prove your result using induction.

Find the smallest $N \in Z^+$ satisfying the property that $n^2 \leq 2^n$ for all $n \geq N$, and prove your result using induction. I assume this can be done simply by testing it will random N ...
0
votes
2answers
111 views

Prove that a set having $n\geq 2$ elements has $\frac{n(n-1)}{2}$ subsets having exactly two elements.

I want to prove this by induction. I have everything up to proving $k+1$. I know I want to show that a set having $k+1$ elements has $\frac{k(k+1)}{2}$ but I'm struggling to find the beginning step ...
1
vote
1answer
67 views

What's wrong with this (fake) proof that $ n=1\forall n\in \Bbb N$?

What's wrong with this (fake) proof that $ n=1\forall n\in \Bbb N$? Base case: $n=1$ true. $n-2,n-1<n+1\implies n-1=n-2\implies n+1=n=1$. From the principle of induction it follows that $n=1 ...
2
votes
2answers
487 views

Induction proof: n lines in a plane

Assume that there are $n$ infinitely long straight lines lying on a plane in such a way that no two lines are parallel, and no three lines intersect at a single point. Prove that these lines divide ...
3
votes
5answers
494 views

Why induction can't work for infinite number? [closed]

Loosely speaking, there is no such number n+1= infinity. Is there any way to prove that induction can not work for infinite numbers in formal way?
0
votes
2answers
80 views

Proving a log by induction

I had a test recently and there was a log question that was $$3\log_3(x) - 4\log_3(x) + 1/2\log_3(x).$$ When I solved it I got $$\log_3 \left(\frac{1}{\sqrt{x}}\right).$$ My teacher says that is ...
4
votes
3answers
65 views

Proof of $n^{1/n} - 1 \le \sqrt{\frac 2n}$ by induction using binomial formula [duplicate]

Using $$(a+b)^{n} = \sum_{i=0}^n {n \choose k} a^{n-k} b^{K}$$ prove that $$n^{1/n} - 1 \le \sqrt{\frac 2n}$$ for n= 2,3,4.... I know the first step is to set $$ n^{\frac 1n} = 1 + x $$ for some ...
0
votes
1answer
33 views

prove the inequality by induction for the folfowing expression

1+1/2+1/3+1/4+.....+1/2^n>=1+n/2 I gOt stuck after 3rd step because I can't represent 3rd expression with the help of second one as there are other numbers between 1/2^k and 1/2^(K+1)
4
votes
4answers
178 views

Proving $(x+y)^n = \sum\limits_{k=0}^n \binom{n}{k} x^k y^{n-k}$ [duplicate]

I'm reading Serge Lang's 'Analysis I', and there's a problem I cannot figure out how to prove: Problem: Prove by induction that $$(x+y)^n = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} x^k ...
0
votes
2answers
56 views

proof by induction, the number of ways of grouping unlabelled objects

How can i prove by induction that, while grouping n unlabelled objects into m groups, $$ f(n,m) = { n+m-1 \choose m-1 }$$ This is the step i could get to, after assuming true for k, for some k+1, I ...
0
votes
2answers
145 views

Graph Proof by induction.

Can you prove via induction that there exists a node in a directed graph of n nodes that can be reached in at most two edges from every other node in the graph. Every node in the graph is required to ...
0
votes
0answers
47 views

Is this a proper way to inductively prove the theta bound of a recurrence relation?

Sorry for the messy work, but it's late. The problem at hand is to find and prove a theta-bound for the following recurrence relation: $T(n) = n{\frac{1}{2}}T(n^{\frac{1}{2}})+nlog(n)$ Claim: ...
1
vote
1answer
61 views

Proof by induction on an inequality

Prove $3^{n+1} > n^4$ such that $n \in \mathbb{N}$, $n \neq 3, n \neq 4$. Let P(n) be the statement "$3^{n+1} > n^4$ such that $n \in \mathbb{N}$, $n \neq 3, n \neq 4$." I have proved the base ...
3
votes
0answers
51 views

Prove $\binom{n}{k} = 0$ for $n = 0, 1, … , k-1$

It's a homework problem. Prove $\binom{n}{k} = 0$ for $n = 0, 1, ... , k-1$ I think induction needs to be used, I can do $n = 0$ (and $n = 1$ since our teacher likes us to do the first two), but $n ...
2
votes
4answers
175 views

Help solving an induction problem…$2^n < n!$ [closed]

Prove the following by induction. k and n in N (natural number) $n^k < 2^n $ $2^n < n! $ Need hint and help please. Thank you very much.
0
votes
1answer
93 views

Prove by induction that if the first car stops, then all cars will stop

$n$ cars are travelling down a narrow one-way street. We know that: The distance $d$ between each two cars is the same. The safe breaking distance $b$ is the minimum distance between ...
4
votes
2answers
55 views

What is the best way to show the monotonicity of this recursive sequence?

This is the sequence: $a_{n+1}$ = $\sqrt{3a_{n} - 2}$ $a_{0}$ = 3 Before evaluating monotonicity I know that the sequence is converting towards either 1 or 2. My approach is to assume it is ...
1
vote
1answer
333 views

Prove by induction for $F(2n) = F(n)[F(n-1) + F(n+1)]$ for all $n\ge 1$

I am totally stumped by this question. I have proved the base case. Then for $k$ is $1$ assume the relation to be true. When I try to prove for $k+1$, the terms just do not simplify to what I want. Is ...
1
vote
2answers
45 views

Prove that $f_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$ for all $n \in \mathbb Z^+$.

Let $\alpha = \frac{1+\sqrt{5}}{2} \hskip 20pt \beta = \frac{1-\sqrt{5}}{2}$ be the two real roots of the quadratic equation $x^2 - x - 1 = 0.$ Prove that $f_n = \frac{\alpha^n - \beta^n}{\alpha - ...
3
votes
1answer
45 views

Proving the gcd of two integers expressed as recursive statements

I have the following problem: Let $a$, $b$ be positive integers and $(x_{n})_{n\geq 0}$ be a sequence of integers defined by the following formulas: $x_{0}=0$, $x_{1}=a$, $x_{n}=x_{n-2}+bx_{n-1}$ ...
-2
votes
1answer
40 views

Prove that for all $n \in \mathbb{Z}^+$, $\sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2$. [duplicate]

Prove that for all $n \in \mathbb{Z}^+$, $\sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2$. I understand how to do the base case using the proof of induction, but I don't know how you would show the ...
1
vote
2answers
33 views

Prove: $n \in Z^{\geq 2}$, $f_nf_{n+1} - f_{n-1}f_{n+2} = (-1)^{n+1}$

$n \in Z^{\geq 2}$, $f_nf_{n+1} - f_{n-1}f_{n+2} = (-1)^{n+1}$. How do you do the inductive step of this proof, every time I do it I cannot find a way to use the definition of a Fibonacci sequence to ...