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

Need help in proving combinatorial identity involving unions, intersections and complements over sets using induction

The identity is the following: $$\left(\bigcap_{i=1}^n (A_i\cup B_i)\right)^C = \bigcup_{i=1}^n (A_i^C\cap B_i^C)$$ I must use induction to prove it. Base. Ok, I think I got how to prove base case: ...
0
votes
2answers
49 views

Prove by Induction: $n \le 3 \sqrt{n} +4$. How to work with the Square-root?

I want to prove the statement $$n \le 3 \sqrt{n} +4$$ for every $n$ belongs to $N$ by induction. So what I have done so far is proving for $p(1)$ is true and assuming that $p(n)$ is true. Now, I ...
1
vote
1answer
68 views

Mathematical induction base case is not initial

Prove by induction that $$1+2+3+\cdots+n= \frac{n(n+1)}{2}$$ for all integers greater than or equal to $2$ How can you solve this if the base case is not $1$? I thought it might be a strong ...
0
votes
2answers
32 views

Use induction to show that $f(n)=2\log_2n+1$

Given is that $$f_n=f_{n/2}+2$$ $n=2^k$ $k=1,2,3...$ and $f(1)=1$ use induction to show that $f(n)=2\log_2n+1$ how do i use induction to solve this?
2
votes
3answers
59 views

Proof by induction that $f(n) = 1-2^{2^n}$, where $f(0) = 3$ and $f(n) = 2 f(n-1) - (f(n-1))^2$

I am doing a textbook question which state that a function $f:\mathbb{N}\to\mathbb{Z}$ is a recursively defined as shown bellow $f(0) =3$, $f(n) = 2\cdot f(n-1) -(f(n-1))^2 $ if $n\ge1$. Prove that ...
1
vote
3answers
73 views

Prove by Induction : $n < 2^n$

So I need to prove the inequality : $$n < 2^n$$ by Induction. What I have done so far is : Step $1$: Prove that the statement is true for $n=1$ $$1<2^1$$ (true) Step $2$: Prove ...
1
vote
2answers
50 views

Help with induction proof for recurrent function

I am having issues with the following inductive proof. Prove by induction on $n$ that $$ a(n) = n!\bigg(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(n-1)!}\bigg)$$ for all $n \geq 1,$ where ...
0
votes
1answer
66 views

Coming up with an alternative proof by induction

Kindly refer to Q4 of this handout. "$2n$ dots are placed around the outside of the circle. $n$ of them are colored red and the remaining $n$ are colored blue. Going around the circle clockwise, you ...
0
votes
1answer
74 views

Show by induction whether $1+\frac{1}{2}+\frac{1}{3}\cdots+\frac{1}{n}$ is an integer or not

How can I show by induction whether $1+\frac{1}{2}+\frac{1}{3}\cdots+\frac{1}{n}$ is an integer or not? Progress : For n=1 the expression is $(=1)$ an integer. How can I show the next step?
0
votes
5answers
85 views

Prove by Induction $64\mid (7^{2n} + 16n − 1)$

We have to show by Mathematical Induction that $64\mid (7^{2n} + 16n − 1).$ Progress : Let us suppose $P(n)$ be the statement i.e., $P(n): 64\mid(7^{2n} + 16n − 1)$ For $n=1$, $(7^{2\cdot ...
2
votes
1answer
74 views

Proof by induction (power rule of the derivative)

Using the differentiation formulas $\displaystyle\frac{d}{dx}x=1$ and $\displaystyle\frac{d}{dx}(fg)=f\frac{dg}{dx}+g \frac{df}{dx}$, prove that $$\frac{d}{dx} x^n=nx^{n-1}$$ for all natural number ...
1
vote
2answers
33 views

Proof by Induction that $3^n ≥ 1+2^n$

Use the PMI to prove the following for all natural numbers: $3^n ≥ 1+2^n$. I have already verified the base case but am having trouble doing so with the inductive case. Thanks!
1
vote
0answers
38 views

RE : Is greatest common divisor of two numbers really their smallest linear combination?

This is in reference to the same proof given in the post Is greatest common divisor of two numbers really their smallest linear combination? I couldn't add a comment there so I'm asking it here. I ...
0
votes
1answer
32 views

Prove that this is true

$$\sum\limits_{i=1}^{n}i^x = P_{x+1}(n)$$ Let x be any nonnegative integer and show that there is a polynomial $P_{x+1}$ of degree $x+1$ for every $n$ greater than or equal to $1$. ...
1
vote
1answer
37 views

How do I use complete induction here?

Suppose currency consists of 3 and 4 cent coins. Suppose you want to buy an item that is worth 9 cents. Show that if you have an unlimited number of 3 and 4 cent coins you can buy anything greater ...
-1
votes
2answers
84 views

Mathematical induction used on Fibonacci Sequence

I have no clue how to go about doing this question using induction. It states that the Fibonacci sequence is defined as: F0 = 0 F1 = 1 Fn = Fn-2 + Fn-1 for n>=2 Let S(n) = Fo + F1 + F2 +...+ ...
1
vote
4answers
37 views

How can I prove this inequality by M.I. or otherwise?

This question is from the past examination: $$f(n)=\frac{2}{3}(n^{3/2}-1)+\sqrt{n}$$ $$g(n)=1+\frac{2}{3}((n+1)^{3/2}-2^{3/2})$$ My task to prove $f(n)≥g(n)$ for all $n≥1$. I have tried M.I here. ...
0
votes
2answers
47 views

Factorials and Mathematical induction

I'm having a bit of trouble understanding mathematical induction, particularly when there's a question with powers or factorials. For example I have a problem 1 x 1! +2 x 2! + 3 x 3! +... + n x n! = ...
2
votes
1answer
38 views

Proof of AM-GM Inequality (setting $a_n$ in the last step) [duplicate]

I have been reading this and this, but I don't understand how one of the step works. Let $a_n=\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}.$ How do you set $a_n$ to meet certain criteria and not lose ...
0
votes
2answers
30 views

Is there some trick to manipulating an equation? (adding 0s, multiplying by 1, etc..)

I have such a hard time doing this sort of thing that it's annoying me. I'm not very mathematically inclined but it frustrates me that a solution with such a small answer takes me more than a page to ...
1
vote
1answer
58 views

What's the correct way of concluding an induction proof?

I had to prove that for every set $s$, the number of subsets with odd cardinalities is $2^{n-1}$. I concluded that this formula holds everytime $|s| \geq 1$ and then I used an inductive process to ...
0
votes
2answers
42 views

An induction question on showing that eventually $(n+2)^n < (n+1)^{n+1}$

Show that eventually $(n+2)^n < (n+1)^{n+1}$ I can see that this is obvious by evaluation at n>2, but I am having a hard time separating to get the induction step within the parenthesis. I am ...
2
votes
3answers
129 views

Counting the number of different ways in which groups of one or two can be formed…

I'm having trouble proving that the number of ways n>3 people can be divided into groups of either one or two is equal to: $A_n = A_{n-1} + (n-1)⋅A_{n-2} $ I'm trying to prove this by counting but ...
0
votes
0answers
39 views

Do I have to prove it by induction with respect to $n$ or to $k$?

I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n-1)$. We have to suppose that $n=2^k, k \geq ...
0
votes
1answer
43 views

Finding $a_n$ if $a_0=a_1=1,a_{n+1}=n(a_n+a_{n-1})\ \ (n\ge 1).$

The problem states: Suppose $a_0,a_1,a_2,...$ is a sequence such that $$a_0=a_1=1,\ \ \ a_{n+1}=n(a_n+a_{n-1})\ \ \ (n\ge 1).$$ Guess a formula for $a_n$, valid for $n\ge 1$, and use mathematical ...
3
votes
1answer
93 views

Prove $\forall n \in N$, every set of natural numbers of size n has a maximum element. May assume that sets do not repeat numbers.

Prove using induction. So i'm a bit confused about how to do this question. My attempt at it seems like i'm missing a lot and it looked to easy. ...
2
votes
2answers
60 views

Can this be proved without making use of derivatives?

Problem: Let $\left(a_{n}\right)$ be a sequence with $a_{1}=1$ and $a_{n+1}=\frac{1}{2}\left(a_{n}+\frac{2}{a_{n}}\right)$. It must be proved that $a_{n}\geq\sqrt{2}$ for $n\geq2$. I have a proof, ...
0
votes
1answer
230 views

Prove through structural induction that a binary tree has an odd number of nodes

A full binary tree is a binary tree where every node has either 0 or 2 children. Prove that every non-empty full binary tree has an odd number of nodes. I dont know how to get started with this ...
0
votes
3answers
28 views

Induction proof for n > 0

Prove using induction the following: for n > 0, 1 ∙ 1! + 2 ∙ 2! + ..... + n ∙ n! = (n + 1)! - 1 I'm not very good at proving proofs with the induction method, help would be greatly appreciated
1
vote
2answers
33 views

Prove using induction principles

$$\forall{n,a>1}:\;\sum\limits_{k=1}^{2^n-1}\frac{1}{k^a}\;\leq\left(\frac{1-2^{n(1-a)}}{1-2^{1-a}}\right)$$ For any fixed value of $a > 1$. Induction step: $$\sum_{k=1}^{2^{n+1} - 1} ...
0
votes
2answers
41 views

Prove this sum of binomial terms using induction.

Here's the problem stumping me today: Let $n \in \mathbb{N}$ and $r \in \mathbb{N}$ such that $r \leq n$, and prove using induction that $\binom{n+1}{r+1} = \sum\limits_{i=r}^n \binom{i}{r}$. I've ...
0
votes
2answers
47 views

Proof by induction steps [duplicate]

Today in class, the instructor is trying to show that for $n \ge 0$, $n < 2^n$. And this are the steps he took: First we assume the inductive hypothesis i.e. $0 < 2^0$, and this is true. Then ...
2
votes
1answer
66 views

Do we have to claim it? If so, at which point?

I have to solve the recurrence relation $$T(n)=\left\{\begin{matrix} 3T\left (\frac{n}{4} \right)+n & , n>1\\ 1 &, n=1 \end{matrix}\right.$$ and prove by induction that the solution I ...
2
votes
2answers
39 views

Chaining Exponent Rules Together

I'm having trouble understanding why the following property is true and want to make sense of it before going ahead and using it in my proof by induction: $$2^{2^n}=2^{2^{n-1}}\times ...
0
votes
2answers
156 views

Prove this induction problem [closed]

Show that every positive integer $N$ less than or equal to $n$ factorial, is the sum of at most $n$ distinct positive integers, each of which divides $n!$.
1
vote
0answers
89 views

Number or regions formed when $n$ points on a circle are joined

The maximum number $R_{n}$ of regions formed when $n$ points on a circle are joined in pairs is $\frac{1}{24}\left(n^{4}-6n^{3}+23n^{2}-18n+24\right)$. This is a fact that I have read in several ...
3
votes
3answers
52 views

Prove $(\log{n})^2\leq 2^n$ by induction

I've trying to solve this for quite a while now, but not being able to finish the proof. Prove using induction that $(\log{n})^2\leq 2^n$
0
votes
1answer
82 views

Mathematical Induction: Sum of first n odd perfect cubes

The series is $$P_k: 1^3 + 3^3 + 5^3 + ... + (2k-1)^3 = k^2(2k^2-1)$$ and I have to replace $P_k$ with $P_{k+1}$ to prove the series. I have to show that $$k^2(2k^2-1) + (2k-1)^3 = ...
4
votes
4answers
328 views

Mathematical Induction Question, Proof Help [duplicate]

Prove using Mathematical Induction that for all natural numbers ($n>0$): $$ \frac 1 {\sqrt{1}} + \frac 1 {\sqrt{2}} + \cdots + \frac 1 {\sqrt{n}} \ge \sqrt{n}. $$ ...
1
vote
3answers
91 views

Mathematical Induction: Sum of first n even perfect squares [duplicate]

So the series is $$P_k: 2^2 + 4^2 + 6^2 + ... + (2k)^2 = \frac{2k(k+1)(2k+1)}3$$ and i have to replace $P_k$ with $P_{k+1}$ to prove the series. I have to show that $$\frac{2k(k+1)(2k+1)}3 + ...
0
votes
1answer
44 views

Follow-up question on mathematical induction with arbitrary base case

Note: This question has already been answered here Proving mathematical induction with arbitrary base using (weak) induction. I was trying to 'reconstruct' at least one proof given in this question ...
0
votes
0answers
67 views

Proof by Induction for Splay Tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay tree ...
5
votes
5answers
472 views

polynomial with positive integer coefficients divisible by 24?

I have to show that $n^4+ 6n^3 + 11n^2+6n$ is divisible by 24 for every natural number, n, so I decided to show that this polynomial is divisible by 8 and 3, but I'm having trouble showing that it is ...
1
vote
1answer
46 views

Prove inequality formula by induction

my question is from Apostol's Vol. 1 One-variable calculus with introduction to linear algebra textbook. Page 35. Exercise 1. Prove the following formula by induction: ...
1
vote
1answer
73 views

prove if $b \geq a$, then $a^{b} \geq b^a$

I found that if b = a - 1, then $a^{b} \leq b^{a}$ and if a = b, then $a^{b} = b^{a}$ for obvious reasons. Now, i'm having a hard time figuring out how to prove that if $b \geq a$, then $a^{b} \geq ...
0
votes
3answers
60 views

prove $m^{m-1} < (m-1)^m$ for m > 3

I found that if m > 3 then $m^{m-1} < (m-1)^m$ for m > 3 seems to hold true for a lot of cases. Can someone prove this inductively ?
1
vote
1answer
126 views

Prove that $(n!)^ 2 \gt n^n$ [duplicate]

Prove the above by by mathematical induction By any other method. I was just asked to prove this so I thought of using mathematical induction. My effort : I started first by verification and ...
1
vote
1answer
42 views

help with understanding a proof

again I'm stuck already on the first steps of an inductive proof of $$ (a+b)^{n+1} = \sum_{k=0}^{n+1} {n+1\choose k}a^kb^{n+1-k} $$ that is, I'm trying to understand the solution to this. It starts ...
2
votes
3answers
58 views

Given the sequence $a_0=1, a_1=2, a_2=3, a_n=a_{n-1}+a_{n-2}+a_{n-3}$, prove by strong induction that for $n\geq 0, a_n \leq 2^n$

I've been trying to work this out for some time and I keep getting stuck. Here is what I have thus far: Base Case: $n=0 ; 1 \leq 1$ $n=1 ; 2 \leq 2$ $n=2 ; 3 \leq 4$ Induction hypothesis: ...
2
votes
1answer
91 views

Strong induction on a summation of recursive functions (Catalan numbers)

I've been stuck on how to proceed with this problem. All that's left is to prove this with strong induction: $$\forall n \in \mathbb{N}, S(n) = \sum_{i=0}^{n-1} S(i)*S(n - 1 - i)$$ Some cases: S(0) ...