Pci-e x16 card vs pci-e x4 motherboard

It may or may not work

If the slot is a full 16x slot with only 4 out of 16 differential pairs hooked up it will work

If the slot is a 4x slot with all 4 differential pairs hooked up it will NOT work because the card will not fit unless you take a hacksaw to it (don't do this)

Most motherboards use only 1x and 16x slots regardless of how many lanes fan out to each of the 16x slots. It is possible to put any PCIe card into a 16x slot even if it was designed for a shorter connector. It will not latch into the slot but it will function.
 
It all depends on what version pci-e slot, 1.0, 2.0, 3.0.

If a 2.0 slot has roughly twice the bandwidth of a 1.0 slot, then that would mean that a pci-e 2.0 at 4x would be roughly the same as a pci-e 1.0 at 8x.

So wouldn't that mean a pci-e 3.0 slot at 4x would be the same as a pci-e 1.0 at 16x?
 


This is correct. Every PCIe generation has doubled the per lane bandwidth from the previous generation. Thus, a 4x PCIe 3.0 link has the same throughput over the period of one second as a 16x PCIe 1.0 link. However, since PCIe are serialized and interleaved the first bytes get from the chipset to the processor faster, drastically lowering the PCIe latency. PCIe 2.0 also had a 20% overhead due to 8b/10b encoding. PCIe 3.0 uses 128b/130b which reduces overhead to <2%