# Tagged Questions

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 ...

24 views

### Full binary tree theorem proof validity?

I'm reviewing some of the theorems that make up the Full binary tree theorem and want to make sure my proof for how the number of internal nodes $I$ is related to the number of total nodes $N$ is ...
5k views

### Questions on “All Horse are the Same Color” Proof by Complete Induction

The following has been bugging me, and I can't go to sleep until I resolve it. Here is a summary of the document on page 109 of http://courses.csail.mit.edu/6.042/spring12/mcs.pdf. False ...
27 views

### Induction Sum of all odd Numbers

Show that $\sum_{k=1}^{n}(2k-1)=n^2$ Beginning: n=1 $\sum_{k=1}^{1}(2k-1)=(2*1-1)=1=1^2$ Let $\sum_{k=1}^{n}(2k-1)=n^2$ be true, then for n=p+1 $\sum_{k=1}^{p+1}(2k-1)=(p+1)^2$ has to be true too....
52 views

### Proving that $\frac{1}{4(5)}+\frac{1}{5(6)}+\frac{1}{6(7)}+\cdots+\frac{1}{(n+3)(n+4)}=\frac{n}{4(n+4)}$ by induction

I've proved the base case where $n=1$ and made the assumption that $n=k$ is true, but I'm stuck on the $n=k+1$ part. I just cannot seem to get the algebra to work in my favor. Here is the original:...
30 views

### Pattern with the the titration of summations.

While dealing with a question with finding an explicit form for a sequence I noticed something: $$\sum_{x_0=0}^{n-1} 1=\frac{n}{1!}$$ $$\sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} 1=\frac{n(n-1)}{2!}$$ ...
99 views

### Prove by induction that $(x+1)^n - nx - 1$ is divisible by $x^2$

Basis step has already been completed. I've started off with the inductive step as just $n=k+1$, trying to involve $f(k)$ into it so that the left over parts can be deducible to be divisible by $x^2$ ...
95 views

### Proof by induction that $169 \mid 3^{3n+3}-26n-27$

$169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $169x= 3^{3n+6}-26n-27-26$ $169x= 27*3^{3n+3}-26n-27-26$ $169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
4k views

### How can you prove that $1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$ without using induction?

Using mathematical induction, I have proved that $$1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$$ for every integer $n > 0$. I would like to know if there is another way of proving this result ...
42 views

### Counting the number of subsets of a set of 2n elements satisfying some conditions.

Let $X =\{v_1, v_2,\cdots, v_n, v_{n+1},\cdots, v_{2n}\}$ be a set of $2n$ elements. I want to find the number of subsets of $X$ with $n$ elements such that both $v_i$ and $v_{n+i}$ are not together ...
85 views

### Rebracketing Theorem

My questions regarding the below theorem Both questions are centred on Eq(2) and the paragraph preceding it. 1) How is it that Eq(2) contains $a_k$ but in that section of the proof the assumption is ...
24 views

### Proof of propositional logic theorem using Induction on Formulas

How to prove the following theorem using induction on formulas? Let V and V' be two valuations of L. Let $\alpha$ be a formula such that V(p) = V'(p), for all atomic formula p that is subformula ...
92 views

### Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$

My question is: Prove by induction that $$3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$$ whenever $n$ is a nonnegative integer. I'm stuck at the basis step. If I ...
21 views

### Prove that the arithmetic-geometric mean inequality holds for any list of numbers whose length is a power of 2

I am self-studying and currently reading How to Prove it by Velleman. I tried to prove the above by induction (I proved that this holds true for $n=2$), but I think my proof is wrong. I only started ...
186 views

### Is this backwards reasoning?

Yesterday I was answering a question on induction: Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear Basically, I was proving a certain formula using ...
44 views

### Prove the n-th Fibonacci number is less than $2^n$ for all n greater than zero using strong induction

I need to prove the n-th Fibonacci number is less than $2^n$ for all $n \geq 0$ using strong induction. I have been exposed to the idea that strong induction differs from weak induction in that the ...
77 views

### understanding a proof which uses induction on the length of a formula

This comes from Shoenfield's textbook Mathematical Logic. Here is the theorem and its proof: If $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators and $u_1\dots u_n$ and $u_1'\dots u_n'$ are ...
31 views